萌新求助无旋treap

加3号点的时候merge死循环了，求助

#include<bits/stdc++.h>
#define R register int
#define N 100005 
using namespace std;
int n,m,rnd[N],lazy[N],val[N],tree[N][0],cnt,rt,x,y,z,size[N];
void maintain(int now) {size[now]=size[tree[now][0]]+size[tree[now][1]]+1;}
void update(int now)
{
    if (lazy[now])
    {
        swap(tree[now][0],tree[now][1]);lazy[now]=0;
        lazy[tree[now][0]]^=1;lazy[tree[now][1]]^=1;
    }
}
void split(int now,int &x,int &y,int k)
{
    if (!now) {x=y=0;return;}
    if (k>size[tree[now][0]]) x=now,split(tree[now][1],tree[now][1],y,k-size[tree[now][0]]-1);
    else y=now,split(tree[now][0],x,tree[now][0],k);
    maintain(now);
}
int merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (rnd[x]<rnd[y])
    {
        update(x);tree[x][1]=merge(tree[x][1],y);
        maintain(x);return x;
    }
    else
    {
        update(y);tree[y][0]=merge(x,tree[y][0]);
        maintain(y);return y;
    }
}
int new_node(int k)
{
    val[++cnt]=k;lazy[cnt]=0;rnd[cnt]=rand();size[cnt]=1;return cnt;
}
void ins(int k) {rt=merge(rt,new_node(k));}
void solve(int l,int r)
{
    split(rt,x,y,l-1);split(y,y,z,r-l+1);
    lazy[y]^=1;rt=merge(x,merge(y,z));
}
void dfs(int now)
{
    if (!now) return;update(now);
    dfs(tree[now][0]);printf("%d ",val[now]);dfs(tree[now][1]); 
} 
int main()
{
    srand(time(0));scanf("%d%d",&n,&m);
    for (R i=1;i<=n;++i) ins(i),printf("???\n");
    for (R l,r,i=1;i<=n;++i) scanf("%d%d",&l,&r),solve(l,r);
    dfs(1);
    return 0;   
}