萌新求助无旋treap

#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;	
}