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

qwq终于把splay调出来了。。。指针这东西有毒，所以换数组重打了一遍。。。 我想了好久为什么翻转区间的时候能直接换子树，换了子树不就不会保持二分查找树的性质了么。。然后发现根本不用保持。。 不bb了，首先为~~我自己~~大家解释一下splay是个啥 ------------ Splay的中文叫伸展树，并且具有二分查找树的性质，就是所有右子树都比根大，所有左子树都比根小。至于为什么叫伸展树，因为它最重要的操作叫做伸展。。 那么伸展是什么咧。就是把一个指定的结点x自底向上逐步旋转到你所需要的某个x的父亲结点。至于怎么转，后面再讲。然后来讲讲为什么要伸展，因为。。~~伸展更健康~~首先伸展可以让整棵树更加平衡，使得树的深度减少便于快速查找。然后对于一些操作比如插入n个元素，删除n个元素。对于插入，你只用把i转到根节点，把i+1转到右子树，i+1必定没有左子树（因为在数列中相邻的，在树上的dfs序也是相邻的），只用在i+1的左子树插入n个元素即可；删除时把i调到根节点，i+n+1调到i的右子树，则i+1到i+n都在i+n+1的左子树上，删除即可。 ------------ 那么接下来是旋转，也就是把当前节点翻到父亲节点（其实我觉得更像是把父亲节点下移）： 因为要保持二分查找树的性质（我也不知道为什么有的时候不用保持。。），所以旋转很奇怪，分一下三种情况： 1.x（当前节点）的父亲节点为根节点   左旋反一下自行脑补。 2.x与x的父亲与x的爷爷（。。就这么叫好了）三点共线 注意要先旋转x的父亲父亲再旋转x，两次同向的旋转    同样另一个情况自行脑补 3.不共线   一样的只不过两次旋转的方向不一样。 ------------ 那么再讲几个操作： 插入和删除已经讲了一半，另一半就是。。怎么找到i和i+1? 首先，你需要给每个节点记一个size，根据size来判断向左找还是向右找。 代码： ```cpp int find(int u,int k) { if(tr[u].tag) pushdown(u);//区间翻转时交换子树的标记下移 int s=tr[tr[u].s[0]].siz; if(k==s+1) return u; if(k<=s) find(tr[u].s[0],k); else find(tr[u].s[1],k-s-1); } ``` 还有就是分裂和合并， 这两个实际上用到的不多，只有变态的移动某一个区间时需要把整一棵子树取出来再合并到另一边去。听着很难，但无非是改一下父亲。。合并就是把两棵子树较小的那一颗的最大结点移到根节点，再把较大子树接到较小子树的根节点的右子树。分裂。。直接把某颗子树的父亲、父亲的左或右节点设为空就行了。这两个操作同样可以在删除一个元素的时候用到，把要删除的x调到根节点，把左右子树分裂，再合并起来就可以了。 然后就是翻转了，也就是这道题目要干的事情。 找到i-1，j+1，给j+1的左儿子改一下标记，有标记就是要交换左右节点，没标记就不用交换，还要像线段树一样把标记传递下去，可以在下一次扫的过程中，边扫边处理。还可以省去某些节点要翻转两次结果不用翻的重复情况。 标记向下传递同时交换左右子树的代码： ```cpp void pushdown(int x) { swap(tr[x].s[0],tr[x].s[1]);//由于是结构体，所有信息都交换了 tr[tr[x].s[0]].tag^=1; tr[tr[x].s[1]].tag^=1; tr[x].tag=0; } ``` 那么操作就到这里 ------------ 这道题的程序： ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,rt; struct node { int s[2]; int val,siz,fa,tag; void clear() { val=0,siz=1; s[0]=s[1]=0; tag=0; } }tr[400100]; void build(int l,int r,int f) { if(l>r) return; int mid=(l+r)/2; tr[mid].clear(),tr[mid].val=mid; if(mid<f) tr[f].s[0]=mid; else tr[f].s[1]=mid; tr[mid].fa=f; if(l==r) return; build(l,mid-1,mid),build(mid+1,r,mid); tr[mid].siz+=tr[tr[mid].s[0]].siz+tr[tr[mid].s[1]].siz; } void pushdown(int x) { swap(tr[x].s[0],tr[x].s[1]); tr[tr[x].s[0]].tag^=1; tr[tr[x].s[1]].tag^=1; tr[x].tag=0; } int find(int u,int k) { if(tr[u].tag) pushdown(u);//找的时候同时下传标记 int s=tr[tr[u].s[0]].siz; if(k==s+1) return u; if(k<=s) find(tr[u].s[0],k); else find(tr[u].s[1],k-s-1); } void rotate(int x,int &k)//旋转，总之就是按上述方法接来接去，想清楚了自然就会打了 { int y=tr[x].fa,z=tr[y].fa,t; t=(tr[y].s[0]==x); if(y==k) k=x; else tr[z].s[tr[z].s[1]==y]=x; tr[y].s[t^1]=tr[x].s[t]; tr[tr[y].s[t^1]].fa=y; tr[x].s[t]=y;tr[y].fa=x;tr[x].fa=z; tr[y].siz=tr[tr[y].s[0]].siz+tr[tr[y].s[1]].siz+1; tr[x].siz=tr[tr[x].s[0]].siz+tr[tr[x].s[1]].siz+1; } void splay(int x,int &k)//伸展函数，在翻转时目的地节点可能会变，所以用了& { while(x!=k) { int y=tr[x].fa,z=tr[y].fa;//取父亲和爷爷 if(y!=k)//分三种情况讨论 { if((x==tr[y].s[0])^(y==tr[z].s[0])) rotate(x,k); else rotate(y,k); } rotate(x,k); } } int main() { scanf("%d%d",&n,&m); rt=(n+3)/2,tr[0].siz=0; build(1,n+2,rt); while(m--) { int l,r; scanf("%d%d",&l,&r); l=find(rt,l),r=find(rt,r+2); splay(l,rt),splay(r,tr[l].s[1]); tr[tr[r].s[0]].tag^=1;//记得要给标记 } for(int i=2;i<=n+1;i++) printf("%d ",find(rt,i)-1); return 0; } ```