直角

#include<bits/stdc++.h>
using namespace std;
int n,m,s[100001],son[100001][2],siz[100001],laz[100001],key[100001],L,R,splx,sply,splz,root,tot;
int upd(int now) {
	siz[now]=siz[son[now][0]]+siz[son[now][1]]+1;
}
void pushdown(int now) {
	if(!laz[now]) return;
	swap(son[now][0],son[now][1]);
	laz[son[now][0]]^=1,laz[son[now][1]]^=1;
}
void split(int now,int k,int &x,int &y) {
	if(!now) x=y=0;
	else if(k==0) x=0,y=now;
	else {
		pushdown(now);
		if(son[now][0]>=k) y=now,split(son[now][0],k,x,son[now][0]);
		else x=now,split(son[now][1],k-son[now][0]-1,son[now][1],y);
		upd(now);
	} 
}
int merge(int x,int y) {
	if(!x||!y) return x+y;
	if(key[x]<key[y]) {
		pushdown(x),son[x][1]=merge(son[x][1],y),upd(x);
		return x;
	}
	else {
		pushdown(y),son[y][0]=merge(x,son[y][0]),upd(y);
		return y;
	}
}
void print(int now) {
	if(!now) return;
	pushdown(now);
	print(son[now][0]);
	++tot,printf("%d ",s[now]);
	print(son[now][1]);
}  
int main() {
	srand(1919810);
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++) {
		s[i]=i,siz[i]=1,key[i]=rand();
		root=merge(root,i);
	}
	while(m--) {
		scanf("%d%d",&L,&R);
		split(root,R,splx,sply),split(splx,L-1,splx,splz);
		laz[splz]^=1;
		root=merge(merge(splx,splz),sply);
	}
	print(root);
	return 0;
}