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

诶，做了题还是写一份题解吧。。。。 这里的Splay维护的显然不再是权值排序 现在按照的是序列中的编号排序（不过在这道题目里面就是权值诶。。。） 那么，继续考虑，其实最终的结果也就是整颗Splay的中序遍历（平衡树的性质诶） 那么，现在如果按照权值来维护显然是不正确的 继续找找规律，发现，如果一个点在序列中的位置为第K个 那么，他就是平衡树的第K大（就当做普通的Splay来看的话） 所以，序列中的位置就变成了区间的第K大点 继续考虑如何翻转 翻转也就是整颗子树的每一个节点的左右儿子交换 因此，只要在根节点的地方打一个标记 在旋转之前下方一下标记就行了 最后输出的时候输出的就是Splay的中序遍历 至于初始的Splay怎么建立，可以直接构造完美的Splay 像我这种比较懒得，直接弄了一个insert。。。 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define MAX 200000 inline int read() { int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t; } struct Node { int ch[2]; int ff,v; int size; int mark; void init(int x,int fa) { ff=ch[0]=ch[1]=0; size=1;v=x;ff=fa; } }t[MAX]; int N,root,M,tot; inline void pushup(int x) { t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1; } inline void pushdown(int x) { if(t[x].mark) { t[t[x].ch[0]].mark^=1; t[t[x].ch[1]].mark^=1; t[x].mark=0; swap(t[x].ch[0],t[x].ch[1]); } } inline void rotate(int x) { int y=t[x].ff; int z=t[y].ff; int k=t[y].ch[1]==x; t[z].ch[t[z].ch[1]==y]=x; t[x].ff=z; t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].ff=y; t[x].ch[k^1]=y; t[y].ff=x; pushup(y);pushup(x); } inline void Splay(int x,int goal) { while(t[x].ff!=goal) { int y=t[x].ff;int z=t[y].ff; if(z!=goal) (t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y); rotate(x); } if(goal==0)root=x; } inline void insert(int x) { int u=root,ff=0; while(u)ff=u,u=t[u].ch[x>t[u].v]; u=++tot; if(ff)t[ff].ch[x>t[ff].v]=u; t[u].init(x,ff); Splay(u,0); } inline int Kth(int k) { int u=root; while(233) { pushdown(u); if(t[t[u].ch[0]].size>=k)u=t[u].ch[0]; else if(t[t[u].ch[0]].size+1==k)return u; else k-=t[t[u].ch[0]].size+1,u=t[u].ch[1]; } } void write(int u) { pushdown(u); if(t[u].ch[0])write(t[u].ch[0]); if(t[u].v>1&&t[u].v<N+2)printf("%d ",t[u].v-1); if(t[u].ch[1])write(t[u].ch[1]); } inline void Work(int l,int r) { l=Kth(l); r=Kth(r+2); Splay(l,0); Splay(r,l); t[t[t[root].ch[1]].ch[0]].mark^=1; } int main() { N=read();M=read(); for(int i=1;i<=N+2;++i)insert(i); while(M--) { int l=read(),r=read(); Work(l,r); } write(root); printf("\n"); return 0; } ```