题解 P3391 【【模板】文艺平衡树（Splay）】

Splay可以用来维护序列。这样的话是把Splay当作一棵区间树。 所谓区间树和权值树的区别，大概就是区间树每个节点代表的是一段区间（典型代表就是一般的线段树） 权值树好理解一点，就是每个点真的代表一个点。 至于翻转操作，我们可以利用Splay的过程实现。详见代码。（Splay能维护序列反转也是它作为**LCT**的辅助树的条件之一） 代码如下 ```cpp #include<bits/stdc++.h> #define N 100005 using namespace std; int n,m; int fa[N],ch[N][2],size[N],rev[N],rt; inline void pushup(int x){ size[x]=size[ch[x][0]]+size[ch[x][1]]+1; } void pushdown(int x){ if(rev[x]){ swap(ch[x][0],ch[x][1]); rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0; } } void rotate(int x,int &k){ int y=fa[x],z=fa[y],kind; if(ch[y][0]==x)kind=1;else kind=0; if(y==k)k=x; else{if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;} ch[y][kind^1]=ch[x][kind];fa[ch[y][kind^1]]=y; ch[x][kind]=y;fa[y]=x;fa[x]=z; pushup(x);pushup(y); } void splay(int x,int &k){ while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k){ if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } void build(int l,int r,int f){ if(l>r)return; int mid=(l+r)/2; if(mid<f)ch[f][0]=mid;else ch[f][1]=mid; fa[mid]=f;size[mid]=1; if(l==r)return; build(l,mid-1,mid);build(mid+1,r,mid); pushup(mid); } int find(int x,int k){ pushdown(x);int s=size[ch[x][0]]; if(k==s+1)return x; if(k<=s)return find(ch[x][0],k); else return find(ch[x][1],k-s-1); } void rever(int l,int r){ int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,ch[x][1]);int z=ch[y][0]; rev[z]^=1; } int main(){ scanf("%d%d",&n,&m); rt=(n+3)/2;build(1,n+2,rt); for(int i=1;i<=m;i++){ int L,R;scanf("%d%d",&L,&R); rever(L,R); } for(int i=2;i<=n+1;i++)printf("%d ",find(rt,i)-1); return 0; } ```