【洛谷】P3391 【模板】文艺平衡树（Splay）

文艺平衡树的Fhq-Treap（无旋treap）做法

与普通平衡树不同的是，这里平衡树需要维护的是一个序列，怎么办呢？

题解

平衡树的性质：无论哪个操作都不会改变树的中序遍历

所以，对于一个序列平衡树来说，可以通过中序遍历来维护整个数组，那么对应的下标为(k)的值就相当于平衡树中的(Kth)。

那么翻转怎么办呢？

其实翻转就相当于恰好包含整个区间的子树将其所有儿子节点的左右子树翻转！
于是就可以通过无旋(treap)来解决这个问题。

每次翻转([l,r])我们就把下标为([1,l-1])，([l,r])，([r+1,n])的区间分别(Split)成三棵树，将([l,r])打上(rev)标记再(Merge)回去。

记住在每一次(Split)和(Merge)操作前将标记下传即可。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=='-'?f=-1:0,ch=getchar());
    for(;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    return x*f;
}
bool rev[100005];
int val[100005],size[100005],ls[100005],rs[100005],pri[100005],R,n,m,cnt;
void Pushdown(int p){if(rev[p])swap(ls[p],rs[p]),rev[ls[p]]^=1,rev[rs[p]]^=1,rev[p]=0;}
void Pushup(int p){size[p]=size[ls[p]]+size[rs[p]]+1;}
void Split(int p,int k,int&rt1,int&rt2){
	if(!p){rt1=rt2=0;return;}
	Pushdown(p);
	if(k<=size[ls[p]]){Split(ls[p],k,rt1,rt2);ls[p]=rt2;rt2=p;}
	else{Split(rs[p],k-size[ls[p]]-1,rt1,rt2);rs[p]=rt1;rt1=p;}
	Pushup(p);
}
int Merge(int rt1,int rt2){
	if(!rt1)return rt2;if(!rt2)return rt1;
	Pushdown(rt1),Pushdown(rt2);
	if(pri[rt1]<pri[rt2]){rs[rt1]=Merge(rs[rt1],rt2);Pushup(rt1);return rt1;}
	else{ls[rt2]=Merge(rt1,ls[rt2]);Pushup(rt2);return rt2;}
}
void Insert(int v){val[++cnt]=v;pri[cnt]=rand();size[cnt]=1;R=Merge(R,cnt);}
void Print(int p){if(!p)return;Pushdown(p);Print(ls[p]);printf("%d ",val[p]);Print(rs[p]);}
int main(){
	n=read(),m=read();
	srand(time(0));
	for(int i=1;i<=n;++i)Insert(i);
	for(int i=1;i<=m;++i){
		int l=read(),r=read(),rt1,rt2,rt3,rt4;
		Split(R,l-1,rt1,rt2);
		Split(rt2,r-l+1,rt3,rt4);
		rev[rt3]^=1;
		R=Merge(rt1,Merge(rt3,rt4));
	}
	Print(R);
}