rt

#include<cstdio>
void swap(int &x,int &y){if(x!=y)x^=y^=x^=y;}
const int N=1e7+1;
int n,m; 
int f[N],ch[N][2],siz[N],tag[N],rt;
void update(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
int to(int x){return ch[f[x]][1]==x;}
void pushdown(int x){
    if(tag[x]){
        swap(ch[x][0],ch[x][1]);
        tag[ch[x][0]]^=1,tag[ch[x][1]]^=1;
		tag[x]=0;
    }
}
void rotate(int x){
	int fa=f[x],gf=f[fa],p=to(x);
	pushdown(x),pushdown(fa);
	f[x]=gf;if(gf)ch[gf][to(fa)]=x;
	ch[fa][p]=ch[x][p^1];
	f[ch[x][p^1]]=fa;
	ch[x][p^1]=fa;f[fa]=x;
	update(fa);update(x);
}
void splay(int x,int k){//我就是这里手残打成int
	for(int fa;(fa=f[x])!=k;rotate(x))
		if(f[fa]!=k)
			rotate(to(x)==to(fa)?fa:x);
	if(!k) rt=x;
}
int build(int l,int r,int fa){
	int mid=(l+r)>>1;
	if(l<mid)ch[mid][0]=build(l,mid-1,mid);
	if(r>mid)ch[mid][1]=build(mid+1,r,mid);
	siz[mid]=1;f[mid]=fa;
	return update(mid),mid;
}
int find(int x){
	int u=rt;
	while(1){
		pushdown(u);
		int v=ch[u][0];
		if(x>1+siz[v]){x-=1+siz[v];u=ch[u][1];}
		else if(x==1+siz[v]) return u;
		else u=v;
	}
}
void reserve(int l,int r){
    int x=find(l),y=find(r+2);
    splay(x,0);splay(y,x);
    tag[ch[ch[x][1]][0]]^=1;
}
int main(){
    scanf("%d%d",&n,&m);
	rt=build(1,n+2,rt);
    for(int i=1,L,R;i<=m;i=-~i){
        scanf("%d%d",&L,&R);
        reserve(L,R);
    }
    for(int i=2;i<=n+1;i=-~i)
		printf("%d ",find(i)-1);
    return 0;
}
```cpp