非旋Treap(fhq treap)

不需要旋转， 只需要分裂 \(Split\) 和合并 \(Merge\)，就可以支持 \(Splay\) 的所有操作。

非常好写，非常好调。

并且支持可持久化（虽然我不会）。

对于每个点需要一个附加权值，根据这个附加权值维护一个小根堆，这样这棵树平衡与否是由这个附加权值决定的，那么这个权值该怎么取呢？随机！

这样 \(Treap\) 就大概是平衡的了。

\(Treap\) 还满足左子 \(<\) 根 \(<\) 右子。

\(Split\)

把一个 \(Treap\) 分成两个，按权值分，把 \(\le v\) 的分在左子树，把 \(> v\) 的分在右子树。

void Split(int p, int v, int &x, int &y)
{
	if(!p) {x = y = 0; return;}
	if(val[p] <= v) x = p, Split(ch[p][1], v, ch[p][1], y);	//如果根的权值<v，就在右子树中split
	else y = p, Split(ch[p][0], v, x, ch[p][0]);	//否则在左子树中split
	pushup(p);
}

\(Merge\)

把两个 \(Treap\) 合成一个，这里就需要用附加权值来保证 \(Treap\) 平衡。

int Merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(dat[x] < dat[y])	//如果x的附加权值小，就把y合并到x的右子树中
	{
		ch[x][1] = Merge(ch[x][1], y);
		pushup(x);
		return x;
	}
	else	//否则，把x合并到y的左子树中
	{
		ch[y][0] = Merge(x, ch[y][0]);
		pushup(y);
		return y;
	}
}

以上就是 fhq treap 的两个基本操作，接下来考虑如何使用。

以洛谷P6136 【模板】普通平衡树（数据加强版）为例。

1.插入一个数 \(v\)

以 \(v\) 为权值分裂 Split(rt, v, x, y)，然后新建一个权值为 \(v\) 的点，再合并 Merge(Merge(x, Newnode(v)), y)。

int Newnode(int v)
{
	val[++cnt] = v;	//权值
	siz[cnt] = 1;	//子树大小
	dat[cnt] = rand(); //附加权值
	return cnt;
}

void Insert(int v)
{
	int x, y;
	Split(rt, v, x, y);
	rt = Merge(Merge(x, Newnode(v)), y);
}

2.删除一个数 \(v\)

void Delete(int v)
{
	int x, y, z;
	Split(rt, v, x, z);	//以 v 为权值分裂
	Split(x, v - 1, x, y);	//以 v-1 为权值在子树 x 中分裂
	//x 的权值是 v-1，y 的权值是 v，因此删掉 y 即可，也就是把 y 的两个孩子合并
	y = Merge(ch[y][0], ch[y][1]);
	//最后将 x y z 合并
	rt = Merge(Merge(x, y), z);
}

3.查询 \(v\) 的排名

以 \(v\) 为权值分裂，排名就是 \(v\) 的左子树的大小 + 1。

int get_rank(int v)
{
	int x, y;
	Split(rt, v - 1, x, y);
	int res = siz[x] + 1;
	rt = Merge(x, y);
	return res;
}

4.查询排名为 \(k\) 的数

跟线段树分治差不多？

如果左子树大小 \(≥ k\)，就在左子树中找排名为 k 的，否则在右子树中找排名为 k - siz[ch[p][0]] - 1 的。

如果当前排名正好为 \(k\)，就直接返回。

int Kth(int p, int k)
{
	if(siz[ch[p][0]] + 1 == k) return p;
	if(siz[ch[p][0]] >= k) return Kth(ch[p][0], k);
	else return Kth(ch[p][1], k - siz[ch[p][0]] - 1); 
}

博主用了递归写法，也可以用 while()。

5.求 \(v\) 的前驱

以 \(v\) 为权值分裂，\(v\) 的前驱即为左子树的最后一个，也就是排名为 siz[x] 的。

int get_pre(int v)
{
	int x, y;
	Split(rt, v - 1, x, y);
	int res = val[Kth(x, siz[x])];
	rt = Merge(x, y);
	return res;
}

6.求 \(v\) 的后继

同样以 \(v\) 为权值分裂，后继即为 \(右子树\) 的第一个，也就是排名为 1 的。

int get_nxt(int v)
{
	int x, y;
	Split(rt, v, x, y);
	int res = val[Kth(y, 1)];
	rt = Merge(x, y);
	return res;
}

注意每次 split 都要记得 merge 不然复杂度无法保证

放一下完整代码

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>

using namespace std;

const int N = 2e6;
int n, m;

int read()
{
	int x = 0;
	char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c)) x = x * 10 + c -'0', c = getchar();
	return x;
}

int rt, cnt, siz[N], ch[N][2], dat[N], val[N];

void pushup(int p)
{
	siz[p] = siz[ch[p][0]] + siz[ch[p][1]] + 1;
}

int Newnode(int v)
{
	val[++cnt] = v;	//权值
	siz[cnt] = 1;	//子树大小
	dat[cnt] = rand();	//附加权值
	return cnt;
}

int Merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(dat[x] < dat[y])	//如果x的附加权值小，就把y合并到x的右子树中
	{
		ch[x][1] = Merge(ch[x][1], y);
		pushup(x);
		return x;
	}
	else	//否则，把x合并到y的左子树中
	{
		ch[y][0] = Merge(x, ch[y][0]);
		pushup(y);
		return y;
	}
}

void Split(int p, int v, int &x, int &y)
{
	if(!p) {x = y = 0; return;}
	if(val[p] <= v) x = p, Split(ch[p][1], v, ch[p][1], y);	//如果根的权值<v，就在右子树中split
	else y = p, Split(ch[p][0], v, x, ch[p][0]);	//否则在左子树中split
	pushup(p);
}

void Insert(int v)
{
	int x, y;
	Split(rt, v, x, y);
	rt = Merge(Merge(x, Newnode(v)), y);
}

void Delete(int v)
{
	int x, y, z;
	Split(rt, v, x, z);	//以 v 为权值分裂
	Split(x, v - 1, x, y);	//以 v-1 为权值在子树 x 中分裂
	//x 的权值是 v-1，y 的权值是 v，因此删掉 y 即可，也就是把 y 的两个孩子合并
	y = Merge(ch[y][0], ch[y][1]);
	//最后将 x y z 合并
	rt = Merge(Merge(x, y), z);
}

int get_rank(int v)
{
	int x, y;
	Split(rt, v - 1, x, y);
	int res = siz[x] + 1;
	rt = Merge(x, y);
	return res;
}


int Kth(int p, int k)
{
	if(siz[ch[p][0]] + 1 == k) return p;
	if(siz[ch[p][0]] >= k) return Kth(ch[p][0], k);
	else return Kth(ch[p][1], k - siz[ch[p][0]] - 1); 
}


int get_pre(int v)
{
	int x, y;
	Split(rt, v - 1, x, y);
	int res = val[Kth(x, siz[x])];
	rt = Merge(x, y);
	return res;
}

int get_nxt(int v)
{
	int x, y;
	Split(rt, v, x, y);
	int res = val[Kth(y, 1)];
	rt = Merge(x, y);
	return res;
}

int main()
{
	srand((unsigned)time(NULL));
	n = read(), m = read();
	for(int i = 1; i <= n; i++)
	{
		int a = read();
		Insert(a);
	}
	int lst = 0, ans = 0;
	while(m--)
	{
		int opt = read(), x = read() ^ lst;
		if(opt == 1) Insert(x);
		else if(opt == 2) Delete(x);
		else if(opt == 3) lst = get_rank(x), ans ^= lst;
		else if(opt == 4) lst = val[Kth(rt, x)], ans ^= lst;
		else if(opt == 5) lst = get_pre(x), ans ^= lst;
		else lst = get_nxt(x), ans ^= lst;
	}
	printf("%d\n", ans);
	return 0;
}