Splay模板

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define rint register int
using namespace std;
template<typename xxx>void read(xxx &x)
{
    x=0;int f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn=100100;
const int inf=0x7fffffff; 
int n,m,tot,rt;
int aa[maxn];
int ch[maxn][2];//ch[i][0]表示i的左儿子，ch[i][1]表示i的右儿子
int val[maxn];//val[i]表示i节点处贮存的值
int cnt[maxn];//cnt[i]表示节点i储存值的个数
int par[maxn];//par[i]表示i节点的父节点
int size[maxn];//size[i]表示i节点的子树储存的权值个数（包括自己）
int rev[maxn];// 
inline bool chk(int x) 
{
    return ch[par[x]][1]==x;//返回x在父节点的方向 
}
inline void pushup(int x) 
{
    size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];//维护个数 
}
inline void rotate(int x)//旋转前后中序遍历的值不变 
{
    int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];
    ch[y][k]=w;par[w]=y;// 旋转后，父节点会将连向需旋转的该子节点的方向的边连向该子节点位于其父节点方向的反方向的节点。
    ch[z][chk(y)]=x;par[x]=z;//旋转后，爷爷节点会将连向父节点的边连向需旋转的该节点。
    ch[x][k^1]=y;par[y]=x;//旋转后，需旋转的该节点会将连向该子节点位于其父节点方向的反方向的子节点的边连向其父节点。
    pushup(y);pushup(x);//注意顺序！！！
}
inline void splay(int x,int goal)//将一个节点一路rotate到指定节点的儿子。 
{
    while(par[x]^goal)
    {
        int y=par[x],z=par[y];
        if(z^goal)
        {
            if(chk(x)==chk(y)) rotate(y);//，如果该节点、该父节点和该爷爷节点「三点一线」，那么应该先旋转父节点。
            else rotate(x);//如果当前点没有祖父 就只用旋转一次 就能到根 直接 rotate 他自己 
        }
        rotate(x);
    }
    if(!goal) rt=x;
}
inline void find(int x)//将最大的小于等于的数所在的节点splay到根 
{ 
    if(!rt) return ;
    int cur=rt;
    while(ch[cur][x>val[cur]]&&x^val[cur]) cur=ch[cur][x>val[cur]]; 
    splay(cur,0);
    //存在值为x的节点时当val[cur]==x跳出循环
    //不存在时ch[cur][x>val[cur]]==0,跳出循环 
}
inline void insert(int x)//插入一个新值 
{
    int cur=rt,p=0;
    while(cur&&val[cur]^x)
    {
        p=cur;
        cur=ch[cur][x>val[cur]];
    }
    if(cur) cnt[cur]++;//存在该节点++ 
    else
    {
        cur=++tot;//没有就新建节点 
        if(p) ch[p][x>val[p]]=cur;//只有一个节点时 
        ch[cur][0]=ch[cur][1]=0;
        val[cur]=x;par[cur]=p;
        cnt[cur]=size[cur]=1;
    }//因为新建节点时可能会拉出一条链，所以新建节点后需要将该节点splay到根节点。沿途的rotate操作可以使平衡树恢复平衡。 
    splay(cur,0);
}
inline int rank(int x)//查询值为x的排名 
{
    find(x); 
    return size[ch[rt][0]];//?????????是否+1
} 
inline int pre(int x)//求前驱 
{
    find(x);
    if(val[rt]<x) return rt;//如果有小于x的数find()后会使其为根节点 
    int cur=ch[rt][0];
    while(ch[cur][1]) cur=ch[cur][1];//否则前驱在左子树的最右节点 
    return cur;
}
inline int succ(int x) //求后继同理 
{
    find(x);
    if(val[rt]>x) return rt;
    int cur=ch[rt][1];
    while(ch[cur][0]) cur=ch[cur][0];
    return cur;
} 
inline void remove(int x) //删除值为x的节点 
{//任何一个数的前驱和后继之间只有它自身。
    int last=pre(x),next=succ(x);
    splay(last,0);splay(next,last);
    int del=ch[next][0];
    if(cnt[del]>1)
    {
        cnt[del]--;
        splay(del,0);
    } 
    else ch[next][0]=0;//判特判权值数大于的情况
    //那么可以考虑把前驱splay到根，后继splay到前驱的右儿子，那么后继的左儿子就是要删除的点。
} 
inline void pushdown(int x)//处理翻转 
{
    if(rev[x])
    {
        swap(ch[x][0],ch[x][1]);//编号变了值没变 
        rev[ch[x][0]]^=1;
        rev[ch[x][1]]^=1;
        rev[x]=0;
    }
} 
inline int kth(int k)//查询第k大 ，返回节点编号 
{
    int cur=rt;
    while(1)
    {
        pushdown(cur);
        if(ch[cur][0]&&k<=size[ch[cur][0]]) cur=ch[cur][0];
        else if(k>size[ch[cur][0]]+cnt[cur]) 
        {
            k-=size[ch[cur][0]]+cnt[cur];
            cur=ch[cur][1];
        }
        else return cur;
    }
}
inline void reverse(int l,int r)
{
    int x=kth(l),y=kth(r+2);//x是第l-1大的节点编号，y是第r+1大的节点编号 
    splay(x,0);splay(y,x);//使x为根节点，y为根的右节点，使第l到第r的区间都在y的右子树上 
    rev[ch[y][0]]^=1;//翻转标记 
}
inline void output(int x)//中序遍历 
{
    pushdown(x);
    if(ch[x][0]) output(ch[x][0]);
    if(val[x]&&1<=val[x]&&val[x]<=n) printf("%d ",val[x]);//注意1<=val[x]&&val[x]<=n是范围由题目决定由 
    if(ch[x][1]) output(ch[x][1]);
}
int main()
{
    read(n);read(m);
    insert(-inf);insert(inf);
    for(rint i=1;i<=n;i++) insert(i);
    for(rint i=1;i<=m;i++)
    {
        int a,b;
        read(a);read(b);
        reverse(a,b);
    }
    output(rt);
}