Splay tree 伸展树：

例①：P3369 【模板】普通平衡树：

题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1。插入x数
2。删除x数(若有多个相同的数，因只删除一个)
3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4。查询排名为xx的数
5。求x的前驱(前驱定义为小于x，且最大的数)
6。求x的后继(后继定义为大于x，且最小的数)
输入格式
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1≤opt≤6 )

输出格式
对于操作3,4,5,63,4,5,6每行输出一个数，表示对应答案

输入输出样例
输入 #1 复制
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出 #1 复制
106465
84185
492737
说明/提示
时空限制：1000ms,128M

1.n的数据范围： n≤100000

2.每个数的数据范围： [-{10} ^ 7, {10} ^ 7]

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int root=0,tot=0;
struct node
{
    int son[2];//子节点
    int fa;//父节点
    int val;//当前节点的值
    int cnt;//当前val的个数
    int si;//子树节点的个数
}t[maxn];

void pushup(int x)
{
    t[x].si=t[t[x].son[0]].si+t[t[x].son[1]].si+t[x].cnt;
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x)
{
    int y=t[x].fa,z=t[y].fa,k=get_son(x),w=t[x].son[k^1];
    t[y].son[k]=w,t[w].fa=y;
    t[z].son[get_son(y)]=x,t[x].fa=z;
    t[x].son[k^1]=y,t[y].fa=x;
    pushup(y),pushup(x);
}

void splay(int x,int goal=0)// 把x旋转到目标goal位置
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(z!=goal)
            if(get_son(x)==get_son(y)) rot(y);
            else rot(x);
        rot(x);
    }
    if(!goal) root=x;
}

void newnode(int &now,int fa,int val)
{
    now=++tot;
    t[now].val=val;
    t[now].fa=fa;
    t[now].si=t[now].cnt=1;
    t[now].son[0]=t[now].son[1]=0;
}

void _insert(int &now,int fa,int val)
{
    if(!now) newnode(now,fa,val),splay(now);
    else if(val<t[now].val) _insert(t[now].son[0],now,val);
    else if(val>t[now].val) _insert(t[now].son[1],now,val);
    else if(val==t[now].val) t[now].cnt++,splay(now);
}

int find_x(int now,int x)//查询权值为x的节点
{
    if(t[now].son[0]&&t[now].val>x) return find_x(t[now].son[0],x);
    else if(t[now].son[1]&&t[now].val<x) return find_x(t[now].son[1],x);
    else
    {
        splay(now);
        return now;
    }
}

int find_son(int now,int k)//查询子树最值节点
{
    while(t[now].son[k]) now=t[now].son[k];
    splay(now);
    return now;
}

int pre(int x)//前驱节点
{
    int p=find_x(root,x);
    if(t[p].val<x) return p;
    return find_son(t[p].son[0],1);
}

int suf(int x)//后继节点
{
    int p=find_x(root,x);
    if(t[p].val>x) return p;
    return find_son(t[p].son[1],0);
}


void del(int x)
{
    int last=pre(x),nt=suf(x);
    splay(last),splay(nt,last);
    int p=t[nt].son[0];
    if(t[p].cnt>1)
    {
        t[p].cnt--;
        splay(p);
    }
    else
    {
        t[nt].son[0]=0;
        splay(nt);
    }
}


int get_rank_by_val(int x)
{
    int p=find_x(root,x);
    return t[t[p].son[0]].si+1;
}

int get_val_by_rank(int now,int rk)//排名为rk的节点
{
    if(t[t[now].son[0]].si<rk&&rk<=t[t[now].son[0]].si+t[now].cnt) return now;
    else if(t[t[now].son[0]].si>=rk) return get_val_by_rank(t[now].son[0],rk);
    else return get_val_by_rank(t[now].son[1],rk-t[t[now].son[0]].si-t[now].cnt);
}


int main(void)
{
    int tt;
    scanf("%d",&tt);
    _insert(root,0,-inf),_insert(root,0,inf);
    int op,x;
    for(int i=1;i<=tt;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==1) _insert(root,0,x);
        else if(op==2) del(x);
        else if(op==3) printf("%d\n",get_rank_by_val(x)-1);
        else if(op==4) printf("%d\n",t[get_val_by_rank(root,x+1)].val);
        else if(op==5) printf("%d\n",t[pre(x)].val);
        else if(op==6) printf("%d\n",t[suf(x)].val);
    }
    return 0;
}

两种不同的写法：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int root=0,tot=0;
struct node
{
    int son[2];//子节点
    int fa;//父节点
    int val;//当前节点的值
    int cnt;//当前val的个数
    int si;//子树节点的个数
}t[maxn];

void pushup(int x)
{
    t[x].si=t[t[x].son[0]].si+t[t[x].son[1]].si+t[x].cnt;
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x,int k)
{
    int y=t[x].fa,z=t[y].fa;

    t[y].son[!k]=t[x].son[k];
    if(t[x].son[k]) t[t[x].son[k]].fa=y;

    t[x].fa=z;
    if(z) t[z].son[t[z].son[1]==y]=x;

    t[y].fa=x;
    t[x].son[k]=y;

    pushup(y),pushup(x);
}

void splay(int x,int goal=0)// 把x旋转到目标goal位置
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(z==goal) rot(x,t[t[x].fa].son[0]==x);
        else
        {
            int k=(t[z].son[0]==y);
            if(t[y].son[k]==x) rot(x,!k),rot(x,k);
            else rot(y,k),rot(x,k);
        }

    }
    if(!goal) root=x;
}


void newnode(int &now,int fa,int val)
{
    now=++tot;
    t[now].val=val;
    t[now].fa=fa;
    t[now].si=t[now].cnt=1;
    t[now].son[0]=t[now].son[1]=0;
}

void _insert(int &now,int fa,int val)
{
    if(!now) newnode(now,fa,val),splay(now);
    else if(val<t[now].val) _insert(t[now].son[0],now,val);
    else if(val>t[now].val) _insert(t[now].son[1],now,val);
    else if(val==t[now].val) t[now].cnt++,splay(now);
}

int find_x(int now,int x)//查询权值为x的节点
{
    if(t[now].son[0]&&t[now].val>x) return find_x(t[now].son[0],x);
    else if(t[now].son[1]&&t[now].val<x) return find_x(t[now].son[1],x);
    else
    {
        splay(now);
        return now;
    }
}

int find_son(int now,int k)//查询子树最值节点
{
    while(t[now].son[k]) now=t[now].son[k];
    splay(now);
    return now;
}

int pre(int x)//前驱节点
{
    int p=find_x(root,x);
    if(t[p].val<x) return p;
    return find_son(t[p].son[0],1);
}

int suf(int x)//后继节点
{
    int p=find_x(root,x);
    if(t[p].val>x) return p;
    return find_son(t[p].son[1],0);
}


void del(int x)
{
    int last=pre(x),nt=suf(x);
    splay(last),splay(nt,last);
    int p=t[nt].son[0];
    if(t[p].cnt>1)
    {
        t[p].cnt--;
        splay(p);
    }
    else
    {
        t[nt].son[0]=0;
        splay(nt);
    }
}


int get_rank_by_val(int x)
{
    int p=find_x(root,x);
    return t[t[p].son[0]].si+1;
}

int get_val_by_rank(int now,int rk)//排名为rk的节点
{
    if(t[t[now].son[0]].si<rk&&rk<=t[t[now].son[0]].si+t[now].cnt) return now;
    else if(t[t[now].son[0]].si>=rk) return get_val_by_rank(t[now].son[0],rk);
    else return get_val_by_rank(t[now].son[1],rk-t[t[now].son[0]].si-t[now].cnt);
}


int main(void)
{
    int tt;
    scanf("%d",&tt);
    _insert(root,0,-inf),_insert(root,0,inf);
    int op,x;
    for(int i=1;i<=tt;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==1) _insert(root,0,x);
        else if(op==2) del(x);
        else if(op==3) printf("%d\n",get_rank_by_val(x)-1);
        else if(op==4) printf("%d\n",t[get_val_by_rank(root,x+1)].val);
        else if(op==5) printf("%d\n",t[pre(x)].val);
        else if(op==6) printf("%d\n",t[suf(x)].val);
    }
    return 0;
}

例②：P3391 【模板】文艺平衡树（Splay）：

题目背景
这是一道经典的Splay模板题——文艺平衡树。

题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入格式
第一行为n,m n表示初始序列有n个数，这个序列依次是 (1,2,⋯n−1,n) m表示翻转操作次数

接下来m行每行两个数 [l,r] 数据保证 1≤l≤r≤n

输出格式
输出一行n个数字，表示原始序列经过m次变换后的结果

输入输出样例
输入 #1 复制
5 3
1 3
1 3
1 4
输出 #1 复制
4 3 2 1 5
说明/提示
n,m≤100000

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int root=0,tot=0,a[maxn];
struct node
{
    int son[2];//子节点
    int fa;//父节点
    int val;//当前节点的值
    int cnt;//当前val的个数
    int si;//子树节点的个数
    int rev;//翻转标记
}t[maxn];

void pushup(int x)
{
    t[x].si=t[t[x].son[0]].si+t[t[x].son[1]].si+t[x].cnt;
}

void pushdown(int x)
{
    if(t[x].rev)
    {
        t[t[x].son[0]].rev^=1;
        t[t[x].son[1]].rev^=1;
        swap(t[x].son[0],t[x].son[1]);
        t[x].rev=0;
    }
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x)
{
    int y=t[x].fa,z=t[y].fa,k=get_son(x),w=t[x].son[k^1];
    pushdown(y),pushdown(x);
    t[y].son[k]=w,t[w].fa=y;
    t[z].son[get_son(y)]=x,t[x].fa=z;
    t[x].son[k^1]=y,t[y].fa=x;
    pushup(y),pushup(x);
}

void splay(int x,int goal=0)// 把x旋转到目标goal位置
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(z!=goal)
            if(get_son(x)==get_son(y)) rot(y);
            else rot(x);
        rot(x);
    }
    if(!goal) root=x;
}

int build(int l,int r,int fa)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int now=++tot;
    t[now].fa=fa;
    t[now].rev=0;
    t[now].cnt=t[now].si=1;
    t[now].val=a[mid];
    t[now].son[0]=build(l,mid-1,now);
    t[now].son[1]=build(mid+1,r,now);
    pushup(now);
    return now;
}

int get_kth(int now,int rk)
{
    pushdown(now);
    if(t[t[now].son[0]].si<rk&&rk<=t[t[now].son[0]].si+t[now].cnt) return now;
    else if(t[t[now].son[0]].si>=rk) return get_kth(t[now].son[0],rk);
    else return get_kth(t[now].son[1],rk-t[t[now].son[0]].si-t[now].cnt);
}

void _reverse(int x,int y)
{
    int l=x-1,r=y+1;
    l=get_kth(root,l),r=get_kth(root,r);
    splay(l),splay(r,l);
    int pos=t[t[root].son[1]].son[0];
    t[pos].rev^=1;
}

void dfs(int now)
{
    if(!now) return ;
    pushdown(now);
    dfs(t[now].son[0]);
    if(t[now].val!=-inf&&t[now].val!=inf)
        printf("%d ",t[now].val);
    dfs(t[now].son[1]);
}


int main(void)
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    a[1]=-inf,a[n+2]=inf;
    for(int i=2;i<=n+1;i++) a[i]=i-1;
    root=build(1,n+2,0);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x++,y++;
        _reverse(x,y);
    }
    dfs(root);


    return 0;
}

上面这个代码pushdown有点问题。。
其实旋转时pushdown用处不大，在找第k大时已经pushdown完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int root=0,tot=0,a[maxn];
struct node
{
    int son[2];//子节点
    int fa;//父节点
    int val;//当前节点的值
    int cnt;//当前val的个数
    int si;//子树节点的个数
    int rev;//翻转标记
}t[maxn];

void pushup(int x)
{
    t[x].si=t[t[x].son[0]].si+t[t[x].son[1]].si+t[x].cnt;
}

void _reveser(int x)
{
    if(!x) return ;
    swap(t[x].son[0],t[x].son[1]);
    t[x].rev^=1;
}

void pushdown(int x)
{
    if(!x) return ;
    if(t[x].rev)
    {
        _reveser(t[x].son[0]);
        _reveser(t[x].son[1]);
        t[x].rev=0;
    }
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x)
{
    int y=t[x].fa,z=t[y].fa;
    pushdown(y),pushdown(x);
    int k=get_son(x),w=t[x].son[k^1];
    t[y].son[k]=w,t[w].fa=y;
    t[z].son[get_son(y)]=x,t[x].fa=z;
    t[x].son[k^1]=y,t[y].fa=x;
    pushup(y),pushup(x);
}

void splay(int x,int goal=0)// 把x旋转到目标goal位置
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(z!=goal)
            if(get_son(x)==get_son(y)) rot(y);
            else rot(x);
        rot(x);
    }
    if(!goal) root=x;
}

int build(int l,int r,int fa)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int now=++tot;
    t[now].fa=fa;
    t[now].rev=0;
    t[now].cnt=t[now].si=1;
    t[now].val=a[mid];
    t[now].son[0]=build(l,mid-1,now);
    t[now].son[1]=build(mid+1,r,now);
    pushup(now);
    return now;
}

int get_kth(int now,int rk)
{
    pushdown(now);
    if(t[t[now].son[0]].si<rk&&rk<=t[t[now].son[0]].si+t[now].cnt) return now;
    else if(t[t[now].son[0]].si>=rk) return get_kth(t[now].son[0],rk);
    else return get_kth(t[now].son[1],rk-t[t[now].son[0]].si-t[now].cnt);
}

void _reverse(int x,int y)
{
    int l=x-1,r=y+1;
    l=get_kth(root,l),r=get_kth(root,r);
    splay(l),splay(r,l);
    int pos=t[t[root].son[1]].son[0];
    _reveser(pos);
}

void dfs(int now)
{
    if(!now) return ;
    pushdown(now);
    dfs(t[now].son[0]);
    if(t[now].val!=-inf&&t[now].val!=inf)
        printf("%d ",t[now].val);
    dfs(t[now].son[1]);
}


int main(void)
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    a[1]=-inf,a[n+2]=inf;
    for(int i=2;i<=n+1;i++) a[i]=i-1;
    root=build(1,n+2,0);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x++,y++;
        _reverse(x,y);
    }
    dfs(root);


    return 0;
}

例③：Robotic Sort HDU - 1890 ：

Somewhere deep in the Czech Technical University buildings, there are laboratories for examining mechanical and electrical properties of various materials. In one of yesterday’s presentations, you have seen how was one of the laboratories changed into a new multimedia lab. But there are still others, serving to their original purposes.

In this task, you are to write software for a robot that handles samples in such a laboratory. Imagine there are material samples lined up on a running belt. The samples have different heights, which may cause troubles to the next processing unit. To eliminate such troubles, we need to sort the samples by their height into the ascending order.

Reordering is done by a mechanical robot arm, which is able to pick up any number of consecutive samples and turn them round, such that their mutual order is reversed. In other words, one robot operation can reverse the order of samples on positions between A and B.

A possible way to sort the samples is to find the position of the smallest one (P1) and reverse the order between positions 1 and P1, which causes the smallest sample to become first. Then we find the second one on position P and reverse the order between 2 and P2. Then the third sample is located etc.

The picture shows a simple example of 6 samples. The smallest one is on the 4th position, therefore, the robot arm reverses the first 4 samples. The second smallest sample is the last one, so the next robot operation will reverse the order of five samples on positions 2–6. The third step will be to reverse the samples 3–4, etc.

Your task is to find the correct sequence of reversal operations that will sort the samples using the above algorithm. If there are more samples with the same height, their mutual order must be preserved: the one that was given first in the initial order must be placed before the others in the final order too.
Input
The input consists of several scenarios. Each scenario is described by two lines. The first line contains one integer number N , the number of samples, 1 ≤ N ≤ 100 000. The second line lists exactly N space-separated positive integers, they specify the heights of individual samples and their initial order.

The last scenario is followed by a line containing zero.
Output
For each scenario, output one line with exactly N integers P1 , P1 , . . . PN ,separated by a space.
Each Pi must be an integer (1 ≤ Pi ≤ N ) giving the position of the i-th sample just before the i-th reversal operation.

Note that if a sample is already on its correct position Pi , you should output the number Pi anyway, indicating that the “interval between Pi and Pi ” (a single sample) should be reversed.
Sample Input
6
3 4 5 1 6 2
4
3 3 2 1
0
Sample Output
4 6 4 5 6 6
4 2 4 4

题意：每次将第 i 小的数，翻转到第 i 个位置。问翻转前第 i 小的数所处的位置。
我们可以每次 i 的id 翻转的根节点，那么它的左子树就是它要翻转的区间。之后将其删除即可。

不过之前的板子好像有问题：
也不知道为什么一直T：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int root=0,tot=0;
struct node
{
    int son[2];//子节点
    int fa;//父节点
    int val;//当前节点的值
    int cnt;//当前val的个数
    int si;//子树节点的个数
    int rev;//翻转标记
}t[maxn];


void pushup(int x)
{
    t[x].si=t[t[x].son[0]].si+t[t[x].son[1]].si+t[x].cnt;
}

void _reveser(int x)
{
    if(!x) return ;
    swap(t[x].son[0],t[x].son[1]);
    t[x].rev^=1;
}

void pushdown(int x)
{
    if(!x) return ;
    if(t[x].rev)
    {
        _reveser(t[x].son[0]);
        _reveser(t[x].son[1]);
        t[x].rev=0;
    }
}


int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x,int k)
{
    int y=t[x].fa,z=t[y].fa;
    pushdown(y),pushdown(x);

    t[y].son[!k]=t[x].son[k];
    if(t[x].son[k]) t[t[x].son[k]].fa=y;

    t[x].fa=z;
    if(z) t[z].son[t[z].son[1]==y]=x;

    t[y].fa=x;
    t[x].son[k]=y;

    pushup(y),pushup(x);
}

void splay(int x,int goal=0)// 把x旋转到目标goal位置
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(z==goal) rot(x,t[t[x].fa].son[0]==x);
        else
        {
            int k=(t[z].son[0]==y);
            if(t[y].son[k]==x) rot(x,!k),rot(x,k);
            else rot(y,k),rot(x,k);
        }

    }
    if(!goal) root=x;
}

void build(int &now,int l,int r,int fa)
{
    if(l>r) return ;
    int mid=(l+r)>>1;
    now=mid;
    t[now].fa=fa;
    t[now].rev=t[now].son[0]=t[now].son[1]=0;
    t[now].cnt=t[now].si=1;
    t[now].val=mid;
    build(t[now].son[0],l,mid-1,now);
    build(t[now].son[1],mid+1,r,now);
    pushup(now);

}

int find_son(int now,int k)
{
    for(pushdown(now);t[now].son[k];pushdown(now)) now=t[now].son[k];
    splay(now,root);
    return now;
}

struct nn
{
    int x,id;
    friend bool operator <(const nn&a,const nn&b)
    {
        if(a.x==b.x) return a.id<b.id;
        else return a.x<b.x;
    }
}a[maxn];

void del_root()
{
    pushdown(root);
    if(!t[root].son[0])
    {
        root=t[root].son[1];
        t[root].fa=0;
        return ;
    }

    int x=find_son(t[root].son[0],1);
    t[x].son[1]=t[root].son[1];
    t[t[root].son[1]].fa=x;
    t[x].fa=0;
    root=x;
    pushup(root);


}

int main(void)
{
    int n,x;
    while(scanf("%d",&n),n)
    {

        for(int i=1;i<=n;i++)
            scanf("%d",&a[i].x),a[i].id=i;
        sort(a+1,a+n+1);

        root=0;
        build(root,1,n,0);

        for(int i=1;i<=n;i++)
        {
            if(i!=1) putchar(' ');
            splay(a[i].id);
            printf("%d",t[t[root].son[0]].si+i);
            _reveser(t[root].son[0]);
            del_root();
        }
        putchar('\n');
    }

    return 0;
}