文艺平衡树（区间翻转）（Splay模板）

这篇blog写的吼啊

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
int fa[N],cnt[N],son[N][3],size[N],key[N],v[N],type,root;
int n,m,a[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')
    {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
bool judge(int x)
{
    return son[fa[x]][1]==x;
}
void up(int x)
{
    size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
void down(int x)
{
    if(x&&v[x])
    {
        v[son[x][0]]^=1;
        v[son[x][1]]^=1;
        swap(son[x][0],son[x][1]);
        v[x]=0;
    }
}
void rotate(int x)
{
    int old=fa[x],oldf=fa[old],lr=judge(x);
    down(old);down(x);
    son[old][lr]=son[x][lr^1];fa[son[old][lr]]=old;
    son[x][lr^1]=old;fa[old]=x;
    fa[x]=oldf;
    if(oldf)son[oldf][son[oldf][1]==old]=x;
    up(old);up(x);
}
void splay(int x,int goal)
{
    for(int f;(f=fa[x])!=goal;rotate(x))
        if(fa[f]!=goal)
            rotate(judge(x)==judge(f)?f:x);
    if(!goal)root=x;
}
int build(int f,int l,int r)
{
    if(l>r)return 0;
    int mid=l+r>>1,now=++type;
    key[now]=a[mid];fa[now]=f;
    v[now]=0;
    son[now][0]=build(now,l,mid-1);
    son[now][1]=build(now,mid+1,r);
    up(now);
    return now;
}
int getrank(int x)
{
    int now=root;
    while(1)
    {
        down(now);
        if(x<=size[son[now][0]])now=son[now][0];
        else
        {
            x-=size[son[now][0]]+1;
            if(!x)return now;
            now=son[now][1];
        }
    }
}
void rev(int l,int r)
{
    l=getrank(l);
    r=getrank(r+2);
    splay(l,0);
    splay(r,l);
    down(root);
    v[son[son[root][1]][0]]^=1;
}
void print(int now)
{
    down(now);
    if(son[now][0])print(son[now][0]);
    if(key[now]!=-0x3f3f3f3f&&key[now]!=0x3f3f3f3f)printf("%d ",key[now]);
    if(key[son[now][1]])print(son[now][1]);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i+1]=i;
    a[1]=-0x3f3f3f3f;a[n+2]=0x3f3f3f3f;
    root=build(0,1,n+2);
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        rev(x,y);
    }
    print(root);
    return 0;
}