splay全挂了求助/kel

QAQ

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,rt,tot,fa[100005],ch[100005][2],cnt[100005],val[100005],sz[100005],tag[100005],num[100005];
inline void maintain(int x)
{
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
inline bool get(int x)
{
    return x==ch[fa[x]][1];
}
inline void push_down(int x)
{
    if(x&&tag[x])
    {
        tag[ch[x][0]]^=1;
        tag[ch[x][1]]^=1;
        ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];
        tag[x]=0;
    }
}
inline void rotate(int x)
{
    int y=fa[x],z=fa[y];
    push_down(x),push_down(y);
    int k=get(x);
    ch[y][k]=ch[x][k^1];
    fa[ch[x][k^1]]=y;
    ch[x][k^1]=y;
    fa[y]=x;
    fa[x]=z;
    if(z)
        ch[z][y==ch[z][1]]=x;
    maintain(y);
    maintain(x);
}
inline void splay(int x)
{
    for(register int f=fa[x];f=fa[x],f;rotate(x))
        if(fa[f])
            rotate(get(f)==get(x)? f:x);
    rt=x;
}
inline int kth(int k)
{
    int node=rt;
    while(1)
    {
        push_down(rt);
        if(ch[node][0]&&k<=sz[ch[node][0]])
            node=ch[node][0];
        else
        {
            k-=sz[ch[node][0]]+cnt[node];
            if(k<=0)
                return val[node];
            node=ch[node][1];
        }
    }
}
inline void update(int x,int y)
{
    y=kth(y+1);
    x=kth(x-1);
    tag[ch[ch[rt][1]][0]]^=1;
}
inline void insert(int k)
{
    if(!rt)
    {
        val[++tot]=k;
        cnt[tot]=1;
        rt=tot;
        maintain(rt);
        return;
    }
    int node=rt,f=0;
    while(1)
    {
        if(val[node]==k)
        {
            ++cnt[node];
            maintain(node);
            maintain(f);
            splay(node);
            return;
        }
        f=node,node=ch[node][k>val[node]];
        if(!node)
        {
            val[++tot]=k;
            cnt[tot]=1;
            ch[f][k>val[f]]=tot;
            fa[tot]=f;
            maintain(tot);
            maintain(f);
            splay(tot);
            return;
        }
    }
}
void dfs(int k)
{
    push_down(k);
    if(ch[k][0])
        dfs(ch[k][0]);
    if(val[k]!=-1&&val[k]!=n+1)
        printf("%d ",val[k]);
    if(ch[k][1])
        dfs(ch[k][1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    insert(-1);
    insert(n+1);
    for(register int i=1;i<=n;++i)
        insert(i);
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        update(l+1,r+1);
    }
    dfs(rt);
    puts("");
    return 0;
}