本地RE

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
	int now=0,nev=1; 
	char c=getchar();
	while(c<'0' || c>'9') 
	{ 
		if(c=='-') 
			nev=-1; 
		c=getchar();
	}
	while(c>='0' && c<='9') 
	{ 
		now=(now<<1)+(now<<3)+(c&15); 
		c=getchar(); 
	}
	return now*nev;
}
const int MAXN=1e6+10;
int n,m;
int rt;
struct tree
{
	int fa;
	int son[3];
	int siz;
	int v;
	int cnt;
	int tag;
}tr[MAXN<<1];
int check_son(int k)
{
	if(tr[tr[k].fa].son[0]==k)
		return 0;
	return 1;
}
void update(int k)
{
	tr[k].siz=tr[tr[k].son[0]].siz+tr[tr[k].son[1]].siz+1;
}
void build(int l,int r,int fa)
{
	if(l>r)
		return ;
	int m=l+r>>1;
	if(m<fa)
		tr[fa].son[0]=m;
	else
		tr[fa].son[1]=m;
	tr[m].fa=fa;
	tr[m].siz=1;
	if(l==r)
		return ;
	build(l,m-1,m);
	build(m+1,r,m);
	update(m);
}
void pushdown(int k)
{
	if(k && tr[k].tag)
	{
		swap(tr[k].son[0],tr[k].son[1]);
		tr[tr[k].son[0]].tag^=1;
		tr[tr[k].son[1]].tag^=1;
		tr[k].tag=0;
	}
}
void connect(int k,int fa,int son)
{
	tr[fa].son[son]=k;
	tr[k].fa=fa;
}
void rotate(int k)
{
	int fa=tr[k].fa;
	int gfa=tr[fa].fa;
	int wson=check_son(k);
	int wfa=check_son(fa);
	connect(tr[k].son[wson^1],fa,wson);
	connect(fa,k,wson^1);
	connect(k,gfa,wfa);
	update(fa),update(k);
}
void Splay(int k,int &to)
{
	while(k!=to)
	{
		int fa=tr[k].fa;
		int gfa=tr[fa].fa;
		if(fa!=to)
		{
			if(check_son(k)==check_son(fa))
				rotate(fa);
			else
				rotate(k);
		}
		rotate(k);
	}
}
int find(int x,int k)
{
	pushdown(x);
	int siz=tr[tr[x].son[0]].siz;
	if(k==siz+1)
		return x;
	if(k<=siz)
		return find(tr[x].son[0],k);
	else
		return find(tr[x].son[1],k-siz-1);
}
void work(int l,int r)
{
	int x=find(rt,l);
	int y=find(rt,r+2);
	Splay(x,rt);
	Splay(y,tr[x].son[1]);
	tr[tr[y].son[0]].tag^=1;
}
int main()
{
	n=read(),m=read();
	rt=(n+3)/2;
	build(1,n+2,rt);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		l=read(),r=read();
		work(l,r);
	}
	for(int i=2;i<=n+1;i++)
		printf("%d ",find(rt,i)-1);
	return 0;
}