FHQ_Treap

废话少说，普通平衡树用 pbds 写写就好了，没必要学，不如直接来学 FHQ_Treap。

文艺平衡树把一个序列放在了二叉树上，满足二叉树的中序遍历是这个序列。这里我们使用 FHQ_Treap 来维护这棵二叉树。

以下的序列在文艺平衡树中都表现为一棵二叉树的中序遍历。
在文艺平衡树中，FHQ_Treap 需要具有以下必需功能

split：把一个长度为 $n$ 的序列从中间某点断开成两个序列，其中第一个序列的长度为 $k$，第二个序列的长度为 $n-k$。
merge：把两个长度为 $x,y$ 的序列实现拼接功能（字符串加法），变成一个长度为 $x+y$ 的序列。

因此每个节点应记录以下信息：

$ls,rs$ 表示该节点的左右儿子
$siz$ 表示子树大小
$pri$ 是每个节点随机分配的优先级，其用途在 merge 中会提到
$val$ 表示为该节点的值

struct node{
	node *ls,*rs;
	int val,pri,siz,tag;
	node(int k=0){
		ls=rs=nullptr;
		val=k;pri=int(rng());siz=1;tag=0;
	}
	node *upd(){
		siz=1+(ls?ls->siz:0)+(rs?rs->siz:0);
		return this;
	}
}

在 split 时，如果发现 $siz_{ls}<k$，说明整个 $ls$ 部分包括当前节点均为第一个序列，我们需要对 $rs$ 继续进行 split，并且第一个序列的根就是 $now$，其左儿子就是 $ls$，而右儿子就是对 $rs$ 继续进行 split 的结果。
否则，就说明整个 $rs$ 部分包括当前节点均为第二个序列，我们需要对 $ls$ 继续进行 split，并且第二个序列的根就是 $now$，其右儿子就是 $ls$，而左儿子就是对 $ls$ 继续进行 split 的结果。

void split(node *now,int k,node *&x,node *&y){
	if(!now){x=y=nullptr;return;}
	int tmp=now->ls?now->ls->siz:0;
	if(tmp<k)x=now,split(now->rs,k-tmp-1,now->rs,y);
	else y=now,split(now->ls,k,x,now->ls);
	now->upd();
}

而对于序列 $x,y$ merge，我们发现有两种合并方法：

把 $x$ 的 $rs$ 和 $y$ 进行 merge，递归处理
把 $x$ 和 $y$ 的 $ls$ 进行 merge，递归处理

为了使树高在 $\log$ 的数量级，我们得选出一种 merge 方法。
可以证明，给每个节点分配一个随机优先级，按照优先级的大小选择 merge 的方法就可以使树高在 $\log$ 的数量级。

node *merge(node *x,node *y){
	if(!x)return y;
	if(!y)return x;
	if(x->pri<y->pri)return x->rs=merge(x->rs,y),x->upd();
	else return y->ls=merge(x,y->ls),y->upd();
}

在序列下标 $k$ 处增加一个元素 $v$，只需先把序列分成长度 $k-1$ 和 $n-(k-1)$ 两部分，然后在中间放个 $v$ 拼起来即可。

void insert(int k,int v){
	node *x=nullptr,*y=nullptr;
	split(rt,k-1,x,y);
	rt=merge(merge(x,new node(v)),y);
}

删除序列下标为 $k$ 的元素，只需先把序列分成长度 $k-1,1,n-k$ 三部分，然后只合并第一、三部分即可。

void erase(int k){
	node *x=nullptr,*y=nullptr,*z=nullptr;
	split(rt,k,x,z);
	split(x,k-1,x,y);
	// y=merge(y->ls,y->rs);
	// rt=merge(merge(x,y),z);
	rt=merge(x,z);
}

访问下标为 $k$ 的元素，只需在树上按照每个节点的 $siz$ 走就行了。

node *kth(node *now,int k){
	for(;;){
		now->pushdw();
		int tmp=now->ls?now->ls->siz:0;
		if(k<=tmp)now=now->ls;
		else if(k==tmp+1)return now;
		else k-=tmp+1,now=now->rs;
	}
}
int operator[](int k){
	return kth(rt,k)->val;
}

上面是基本操作，即 $\mathcal O(\log n)$ 时间复杂度的插入、删除、随机访问。文艺平衡树还有一个经典操作是区间翻转。
我们发现，如果我们要把区间 $[l,r]$ 翻转，只需先 split 出这一段序列，然后将这棵二叉树上每个节点的左右儿子互换就实现了区间翻转。
可是这样子复杂度不对，但是可以打 lazy tag，由于所有操作都是基于 split 和 merge 的，所以只需在 split 和 merge 时下传标记。
不过 kth 没有用到 split 和 merge，所以 kth 时也要下传标记。

struct treap{
	struct node{
		node *ls,*rs;
		int val,pri,siz,tag;
		node(int k=0){
			ls=rs=nullptr;
			val=k;pri=int(rng());siz=1;tag=0;
		}
		node *upd(){
			siz=1+(ls?ls->siz:0)+(rs?rs->siz:0);
			return this;
		}
		node *pushdw(){
			if(!tag)return this;
			if(ls)ls->tag^=1,swap(ls->ls,ls->rs);
			if(rs)rs->tag^=1,swap(rs->ls,rs->rs);
			tag=0;
			return this;
		}
	}*rt=nullptr;
	node *merge(node *x,node *y){
		if(!x)return y;
		if(!y)return x;
		x->pushdw();y->pushdw();
		if(x->pri<y->pri)return x->rs=merge(x->rs,y),x->upd();
		else return y->ls=merge(x,y->ls),y->upd();
	}
	void split(node *now,int k,node *&x,node *&y){
		if(!now){x=y=nullptr;return;}
		now->pushdw();
		int tmp=now->ls?now->ls->siz:0;
		if(tmp<k)x=now,split(now->rs,k-tmp-1,now->rs,y);
		else y=now,split(now->ls,k,x,now->ls);
		now->upd();
	}
	node *kth(node *now,int k){
		for(;;){
			now->pushdw();
			int tmp=now->ls?now->ls->siz:0;
			if(k<=tmp)now=now->ls;
			else if(k==tmp+1)return now;
			else k-=tmp+1,now=now->rs;
		}
	}
	int operator[](int k){
		return kth(rt,k)->val;
	}
	void insert(int k,int v){
		node *x=nullptr,*y=nullptr;
		split(rt,k-1,x,y);
		rt=merge(merge(x,new node(v)),y);
	}
	void erase(int k){
		node *x=nullptr,*y=nullptr,*z=nullptr;
		split(rt,k,x,z);
		split(x,k-1,x,y);
		// y=merge(y->ls,y->rs);
		// rt=merge(merge(x,y),z);
		rt=merge(x,z);
	}
	void reverse(int l,int r){
		node *x=nullptr,*y=nullptr,*z=nullptr;
		split(rt,r,x,z);
		split(x,l-1,x,y);
		swap(y->ls,y->rs);
		y->tag^=1;
		rt=merge(merge(x,y),z);
	}
}