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

/*https://blog.csdn.net/clove_unique/article/details/50630280*/#include
      
       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]
       
        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维护下标，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
      
       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*/