//洛谷在线IDE
运行成功 82ms 612kb

https://www.luogu.com.cn/record/47426814 全MLE了 代码

#include<iostream>
using namespace std;
int siz[100001],ch[100001][2];
int fa[100001],cnt[100001]
,val[100001];
bool tag[100001];
int root=0,n,m,tot=0;
void pushup(int x)
{
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
void pushdown(int x)
{
	if(x&&tag[x]==1)
	{
		tag[x]=0;
		tag[ch[x][0]]^=1;
		tag[ch[x][1]]^=1;	
		swap(ch[x][0],ch[x][1]);
	
	}
}
int son(int x)
{
	pushdown(x);
	if(x==ch[fa[x]][0]) return 0;
	else return 1;
}
void rotate(int x)
{
	int y=fa[x];
	pushdown(y);
	pushdown(x);
	int zch=ch[x][!son(x)];
	int gr=fa[y];
	bool yy=son(y),xx=son(x);
	ch[gr][yy]=x;fa[x]=gr;
	ch[x][!xx]=y;fa[y]=x;
	ch[y][xx]=zch;fa[zch]=y;
	pushup(y);pushup(x);
}
int splay(int x,int y)
{
	while(fa[x]!=y)
	{
		int fat=fa[x];
		int z=fa[fat];
		if(z==y)
			rotate(x);
		else if(son(fat)==son(x)) 
		{
			rotate(fat);
			rotate(x);
		}
		else
		{
			rotate(x);
			rotate(x);
		}
	}
	if(y==0) root=x;
}
void insert(int x)
{
	int u=root,ff=0;
	while(u&&val[u]!=x)
	{
		ff=u;
		u=ch[u][x>val[u]];
	}
	if(u) cnt[u]++;
	else
	{
		u=++tot;
		if(ff)
			ch[ff][x>val[ff]]=u;
		ch[tot][0]=0;
		ch[tot][1]=0;
		fa[tot]=ff; val[tot]=x;
		cnt[tot]=1; 
	}
	splay(u,0);
}
int find(int k)
{
	int now=root;
	while(1)
	{
		pushdown(now);
		if (k<=siz[ch[now][0]])
			now=ch[now][0];
		else
		{
			k-=siz[ch[now][0]]+1;
			if (!k) return now;
			now=ch[now][1];
		}
	}
}
void pri(int ro)
{
	pushdown(ro);
	if(ch[ro][0]) pri(ch[ro][0]);
	if(val[ro]!=-2147483647&&val[ro]!=2147483647) cout<<val[ro]<<" ";
	if(ch[ro][1]) pri(ch[ro][1]);
}
int main()
{
	insert(-2147483647);
	insert(2147483647);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		insert(i);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		int l_=find(l),r_=find(r+2);
		splay(l_,0);
		splay(r_,l_);
		tag[ch[ch[root][1]][0]]^=1;
	}
	pri(root);
	return 0;
}