救救孩子吧 必关

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int rt=0,sz=0;
int w[MAXN],s[MAXN],ch[MAXN][2];
bool rev[MAXN];
void update(int k)
{
	s[k]=s[ch[k][0]]+s[ch[k][1]]+1;
}
int push_down(int k)
{
	if(rev[k])
	{
		swap(ch[k][0],ch[k][1]);
		if(ch[k][0])rev[ch[k][0]]^=1;
		if(ch[k][1])rev[ch[k][1]]^=1;
		rev[k]=0;
	}
}
void split_kth(int now,int k,int &x,int &y)
{
	if(!now)x=y=0;
	else
	{
		push_down(now);
		if(k<=s[ch[now][0]])y=now,split_kth(ch[now][0],k,x,ch[now][0]);
		else x=now,split_kth(ch[now][1],k-s[ch[now][0]]-1,ch[now][1],y);
		update(now);
	}
}
int merge(int x,int y)
{
	if(!x||!y)return x+y;
	if(w[x]<w[y])
	{
		push_down(x);
		ch[x][1]=merge(ch[x][1],y);
		update(x);
		return x;
	}
	else
	{
		push_down(y);
		ch[y][0]=merge(x,ch[y][0]);
		update(y);
		return y;
	}
}
int new_node(int _v)
{
	++sz;
	w[sz]=rand();
	s[sz]=1;
	ch[sz][0]=ch[sz][1]=0;
	return sz;
}
void insert(int &root,int v)
{
	int x,y;
	split_kth(root,v,x,y);
	root=merge(merge(x,new_node(v)),y);
}
void update(int &root,int l,int r)
{
	int x,y,z;
	split_kth(root,r,x,z);
	split_kth(x,l-1,x,y);
	rev[y]^=1;
	root=merge(merge(x,y),z);
}
void query(int root)
{
	if(!root)return;
	push_down(root);
	query(ch[root][0]);
	cout<<root<<" ";
	query(ch[root][1]);
}
int main()
{
	srand(time(0));
	int n,m,l,r;
	cin>>n>>m;
	for(int i=1;i<=n;i++)insert(rt,i);
	while(m--)
	{
		cin>>l>>r;
		update(rt,l,r);
	}
	query(rt);
	return 0;
}