FHQ平衡树

实质：

FHQ平衡树又称无旋Treap。（即通过\(Split 与Merge\)来替代旋转。）

本质上还是一颗二分查找树，再利用随机数来维护相对平衡的树形结构。

实现：

\(Node\)：对于每个节点维护\(siz, pri,key,ls,rs\)。

struct node{int ls, rs, pri, siz, key;}

\(Split\)：

void split(int i, int x, int &L, int &R){
	if(!i){L = R = 0; return ;}
	if(t[i].key <= x) 
		L = i, split(t[i].rs, x, t[L].rs, R);
	else 
		R = i, split(t[i].ls, x, L, t[R].ls);
	update(i);
}

\(Merge\):

int merge(int L, int R){
	if(!L || !R) return L + R;
	if(t[L].pri < t[R].pri){
		t[R].ls = merge(L, t[R].ls);
		update(R);
		return R;
	}else{
		t[L].rs = merge(t[L].rs, R);
		update(L);
		return L;
	}
}

\(Newnode\):

int new_node(int x){
	t[++cnt].siz = 1;
	t[cnt].key = x;
	t[cnt].pri = Rnd();
	return cnt;
}

\(Insert\):

void insert(int x){
	split(root, x - 1, L, R);
	rt = merge(merge(L, new_node(x)), R);
}

\(Query\):

int query(int x){
	int ans;
	split(root, x - 1, L, R);
	ans = t[L].siz + 1;
	rt = merge(L, R);
	return ans;
}

\(Delete\):

void del(int x){
	int M;
	split(rt, x, L, R);
	split(L, x - 1, L, M);
	M = merge(t[M].ls, t[M].rs);
	rt = merge(merge(L, M), R);
}

\(Kth\):

int kth(int i, int k){
	if(k == t[t[i].ls].siz + 1) return i;
	if(k <= t[t[i].ls].siz) return kth(t[i].ls, k);
	if(k > t[t[i].ls].siz) return kth(t[i].rs, k - t[t[i].ls].siz - 1);
}

\(Pre\):

int pre(int x){
	int ans;
	split(rt, x - 1, L, R);
	ans = t[kth(L, t[L].siz)].key;
	rt = merge(L, R);
	return ans;
}

\(Suf\):

int suf(int x){
	int ans;
	split(root, x, L, R);
	ans = t[kth(R, 1)].key;
	root = merge(L, R);
	return ans;
}