求救大佬

程序被样例卡了。 由于在第三次修改操作时死循环，经调试目前初步确定问题出在kth（）中。虽本人先学过treap，又对照了大佬的程序，但还是无法找出问题所在，特此求救。

debug没删，大佬可以试一下，谢谢

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
int n,m;

int ch[100005][2],fa[100005],v[100005];
int s[100005],c[100005],lazy[100005];int rt=0,cned=0;

int chk(int x) {return ch[fa[x]][1]==x;}
void pushup(int x) {s[x]=s[ch[x][0]]+s[ch[x][1]]+c[x];} 
void pushdown(int x)
{
    if(lazy[x])
    {
        swap(ch[x][0],ch[x][1]);
        lazy[ch[x][0]]^=1;lazy[ch[x][1]]^=1;
        lazy[x]=0;
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
    ch[x][k^1]=y;fa[y]=x;
    ch[y][k]=w;fa[w]=y;
    ch[z][chk(y)]=x;fa[x]=z;
    pushup(y);pushup(x);//顺序要注意 
}
void splay(int x,int goal=0)
{
    while(fa[x]!=goal)
    {
        int y=fa[x],z=fa[y];
        if(z!=goal)
            if(chk(x)==chk(y)) rotate(y);
            else rotate(x);
        rotate(x);
    }
    if(!goal) rt=x;
}
void insert(int k)
{
    int x=rt,y=0;
    while(x and v[x]!=k)
        y=x,x=ch[x][k>v[x]];
    if(x) c[x]++;
    else 
    {
        x=++cned;
        ch[y][k>v[y]]=x;
        ch[x][0]=ch[x][1]=0;
        fa[x]=y;v[x]=k;
        s[x]=c[x]=1;
    } 
    splay(x);
}
int kth(int k)
{
    int x=rt;
    while(x)
    {//此处卡循环 
        pushdown(x);//printf("***");
        if(k>s[ch[x][0]] and k<=s[ch[x][0]]+c[x]) return x;
        else if(k<=s[ch[x][0]]) x=ch[x][0];
             else k-=s[ch[x][0]]+c[x],x=ch[x][1];
    }
    return x;
}int cnt=0;
void revise(int l,int r)
{
    int x=kth(l);//printf("@@%d\n",++cnt);
    int y=kth(r+2);
    //printf("##%d %d %d \n",cnt,x,y);
    splay(x);splay(y,x);
    lazy[ch[y][0]]^=1;
}
void output(int x)
{
    pushdown(x);
    if(ch[x][0]) output(ch[x][0]);
    if(v[x]>2 and v[x]<n+2) printf("%d ",v[x]-1);
    if(ch[x][1]) output(ch[x][1]);
}
int main()
{
    scanf("%d%d",&n,&m);int l,r;
    for(int i=1;i<=n+2;i++) insert(i);
    while(m--)
    {
        scanf("%d%d",&l,&r);
        revise(l,r);
    } 
    output(rt);
    return 0;
}