模板存一下：求前驱后继，求x的排名和排在的x名的数，删除和插入一个数。

/*/clove_unique/article/details/50630280*/#include<bits/stdc++.h>using namespace std;#define N 100005#define INF 2100000000int f[N],ch[N][5],key[N],siz[N],cnt[N],sz=0,root=0;void clear(int x){ ch[x][1]=ch[x][0]=f[x]=cnt[x]=siz[x]=0;key[x]=-INF;} void update(int x){if(!x) return ;siz[x]=cnt[x];if(ch[x][0]) siz[x]+=siz[ch[x][0]];//记得是siz！！ if(ch[x][1]) siz[x]+=siz[ch[x][1]];}int get(int x)//返回x是左儿子还是右儿子 {return (ch[f[x]][1]==x);}void ro(int x)//旋转操作 {int old=f[x],oldf=f[f[x]],wi=get(x);//父亲 父亲的父亲 wi判断是左儿子还是右儿子 ch[old][wi]=ch[x][wi^1]; f[ch[old][wi]]=old;//父亲的原儿子接到与x关系相反的儿子 那个儿子自己也将父亲变成它 f[old]=x; ch[x][wi^1]=old; //自己变成父亲的父亲 父亲变成方向相反的儿子 f[x]=oldf;//自己的父亲变成父亲的父亲 if(oldf) ch[oldf][ch[oldf][1]==old]=x;//父亲的父亲的儿子也变成自己 替补到old的位置上去 update(old); update(x);//先update深度大的！！ }void splay(int x){for(int fa;(fa=f[x]);ro(x))if(f[fa])//父亲的父亲要存在 因为要旋到f[fa]的儿子 ro((get(x)==get(fa)?fa:x));//如果x与fa在一条直线上就应该先旋fa root=x;//已经把x旋转到根 就应该记录一下！！ }void add(int v)//插入值为v的点 {//sz是节点的编号 if(root==0) { sz++; ch[sz][0]=ch[sz][1]=f[sz]=0; key[sz]=v; cnt[sz]=1; siz[sz]=1; root=sz; return ; }int now=root,fa=0;//从根节点开始找位置 while(1){if(key[now]==v)//已经有了这个点 就直接在cnt上++(二叉平衡树不能有重复的点) 还要记得旋一下 {cnt[now]++; update(now); update(fa); splay(now); break;}fa=now; now=ch[now][key[now]<v];//key[now]<v便于判断是在左边还是右边 if(now==0)//新建一个节点 {sz++; ch[sz][0]=ch[sz][1]=0; f[sz]=fa; cnt[sz]=1; siz[sz]=1; key[sz]=v;ch[fa][key[fa]<v]=sz;//将father的左或右儿子赋成sz update(fa); splay(sz);//把新建的节点旋到根 而不是now break;}}}int find(int v)//找到值为v的数的排名{int now=root,ans=0;while(1){//printf("la:%d ",now);if(v<key[now]) now=ch[now][0];else{ans+=(ch[now][0]?siz[ch[now][0]]:0);//如果now的左儿子存在的话就 + 否则不加 //find的时候要是splay一下 保证时间复杂度！！ if(key[now]==v) { splay(now); return ans+1; }ans+=cnt[now]; now=ch[now][1];}}}int kth(int x)//找到的第x名的数 {int now=root;while(1){if(ch[now][0]&&x<=siz[ch[now][0]]) now=ch[now][0];//随时都要判断是否存在儿子 记得有<=!! else{int p=(ch[now][0]?siz[ch[now][0]]:0)+cnt[now];//记得考虑它本身的出现次数 if(x<=p) return key[now];x-=p; now=ch[now][1]; }}}//进行找前驱后继时会先把x旋转到根 所以不用传值进去 int q_pre()//前驱是第一个小于x的 利用二叉树的性质 找左子树中最靠右的 {int now=ch[root][0];while(ch[now][1]) now=ch[now][1];////return now;}int q_hou(){int now=ch[root][1];while(ch[now][0]) now=ch[now][0];return now;}void dele(int x){int blala=find(x);if(cnt[root]>1) { cnt[root]--; update(root); return ; }//个数减少了记得update if(!ch[root][0]&&!ch[root][1]) { clear(root); root=0; return ; }if(!ch[root][0]) { int oldrt=root; root=ch[root][1]; f[root]=0; clear(oldrt); return ; }else if(!ch[root][1]){ int oldrt=root; root=ch[root][0]; f[root]=0; clear(oldrt); return ; } //有两个及以上的儿子int qian=q_pre(),oldrt=root;splay(qian);//将前驱旋到根 f[ch[oldrt][1]]=root; ch[root][1]=ch[oldrt][1];//把原根的右子树接在新根上 clear(oldrt); update(root);//清理旧根 update新根 }int main(){int n,x,op;scanf("%d",&n);while(n--){scanf("%d%d",&op,&x);if(op==1) add(x);else if(op==2) dele(x);else if(op==3) printf("%d\n",find(x));else if(op==4) printf("%d\n",kth(x));else if(op==5) add(x),printf("%d\n",key[q_pre()]),dele(x);else if(op==6) add(x),printf("%d\n",key[q_hou()]),dele(x); }return 0;}/*101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598101 51 31 61 21 41 73 5*/

splay模板

题意：给一个初始序列，求经过若干次区间翻转后的序列。

思路：

维护什么？用splay维护下标，key值存下标对应的值，如序列：1 3 4 2 则1存的key值是1，2存的key值是3，3存的key值是4，4存的key值是2.

怎么翻转？当要翻转l和r的时候，先找到l和r这两个下标对应splay中的编号（sply节点的编号），然后将l-1旋转到根，r+1旋转到根的右儿子，由于中序遍历的有序性，[l,r]这个区间就在r+1的左子树，如此操作就实现了区间的提取。提取区间后，先对其打上一个翻转标记，当需要查询是，将翻转标记下传，一层一层地将左右子树翻转，实现区间翻转。

为什么翻转之后找rank还能找对?这里的rank函数其实是找到下标对应splay的节点编号，而下标的中序遍历是有序的，那么通过siz的比较就可以找到对应位置

而这道题的下标和值域对应的初始值是一样的，不要弄混了。

/*洛谷P3391 【模板】文艺平衡树Splay题意：求区间翻转后的序列思路：把l-1旋到根 r+1旋到l-1的右儿子 这样r+1的左儿子就是l到r这段区间 实现了区间的提取splay的性质：中序遍历一直是有序的 所以区间的翻转就可以 */#include<bits/stdc++.h>using namespace std;#define inf 0x7f7f7f#define N 100005//数组不用加倍 因为平衡树一个点对应一个点 而不是一段区间 #define mid ((l+r)>>1)int ch[N][3],siz[N],key[N],fl[N],a[N],ndnum=0,root=0,fa[N];void update(int s){ siz[s]=siz[ch[s][0]]+siz[ch[s][1]]+1; }//+1因为有它自己 int build(int f,int l,int r){if(l>r) return 0;int s=++ndnum;key[s]=a[mid]; fa[s]=f; fl[s]=0;ch[s][0]=build(s,l,mid-1);//注意与线段树的差异：s记录的是mid这个点 而它的左右儿子分别记录l~mid-1 mid+1~r ch[s][1]=build(s,mid+1,r);update(s);return s;}int get(int x){ return (ch[fa[x]][1]==x) ; }void pushdown(int x){if(x&&fl[x]){fl[ch[x][0]]^=1;//向左右儿子传标记 fl[ch[x][1]]^=1;swap(ch[x][0],ch[x][1]);//区间翻转 fl[x]=0;}}void rotate(int x){int old=fa[x],oldf=fa[old],which=get(x);ch[old][which]=ch[x][which^1];fa[ch[old][which]]=old;fa[old]=x; ch[x][which^1]=old;fa[x]=oldf;if(oldf) ch[oldf][ch[oldf][1]==old]=x;update(old),update(x);}void splay(int x,int tt)//将x旋到tt的儿子节点 {//其实这个操作旋了两次 一次是for结束时 一次是if判断后 for(int f;(f=fa[x])!=tt;rotate(x))//判断旋两次后能不能到tt的儿子节点 如果能到 就不用旋了 直接通过for循环来旋 if(fa[fa[x]]!=tt) rotate(get(x)==get(f)?f:x);//如果在一条直线 就要先旋fa if(!tt) root=x; }int rank(int x){int now=root;while(1){pushdown(now);//查找排名时记得下传标记 if(x<=siz[ch[now][0]]) now=ch[now][0];else{x=x-siz[ch[now][0]]-1;//与线段树不同的是 它不仅要减去儿子节点 还要减去它自己 因为它自己存了mid这个点 if(!x) return now;now=ch[now][1];}}}void turn(int l,int r){int x=rank(l),y=rank(r+2);//因为维护的是值域平衡树 所以要先找到在平衡树中的排位(也就是说对应着哪个点) splay(x,0); splay(y,x);//把x旋到根节点(0是因为根的父亲是0) 把y旋到x的右节点 fl[ch[ch[root][1]][0]]^=1;}void dfs(int now){pushdown(now);if(ch[now][0]) dfs(ch[now][0]);if(key[now]!=-inf&&key[now]!=inf) printf("%d ",key[now]);//注意是key里面存储真正的值 而now只是平衡树的节点 if(ch[now][1]) dfs(ch[now][1]);}int main(){int n,m,l,r;scanf("%d%d",&n,&m);for(int i=2;i<=n+1;i++) a[i]=i-1;a[1]=-inf; a[n+2]=inf;root=build(0,1,n+2);//根是0 注意是1 到 n+2 因为加了正无穷和负无穷 while(m--){scanf("%d%d",&l,&r);turn(l,r);}dfs(root);}/*5 31 31 31 4*/

文艺平衡树

如果觉得《平衡树（模板+文艺平衡树）》对你有帮助，请点赞、收藏，并留下你的观点哦！