不知为啥全部超时了。。样例和数据1都没有问题 在线IDE也只跑了100ms不到（数据一

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000008;
int n,m,x,y,cnt,val[maxn],rnd[maxn],z,root;
int child[maxn][2],size[maxn],rev[maxn];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
void swap(int &x1,int &y1){
	int z=x1;x1=y1;y1=z;
}
void pushup(int x){
	size[x]=size[child[x][0]]+size[child[x][1]]+1;
}
void pushdown(int rt){
	if(rev[rt]){
		swap(child[rt][0],child[rt][1]);
		if(child[rt][0])rev[child[rt][0]]^=1;
		if(child[rt][1])rev[child[rt][1]]^=1;
		rev[rt]=0;
	}
}
int merge(int a,int b){
	if(!a||!b)return a+b;
	if(rnd[a]<rnd[b]){if(rev[a])pushdown(a);child[a][1]=merge(child[a][1],b);pushup(a);return a;}
	else {if(rev[b])pushdown(b);child[b][0]=merge(a,child[b][0]);pushup(b);return b;}
}
int randoom() {
    return rand() << 15 | rand();
}
int newcode(int x){
	size[++cnt]=0;
	val[cnt]=x;
	rnd[cnt]=randoom();
	return cnt;
}
void split(int now,int k,int &x,int &y){
	if(!now){x=y=0;return;}
	if(rev[now])pushdown(now);
	if(k<=size[child[now][0]]){y=now;split(child[now][0],k,x,child[now][0]);}
	else {x=now;split(child[now][1],k-size[child[now][0]]-1,child[now][1],y);}
    pushup(now);
}
int insert(int &k,int a){
	split(k,a,x,y);
	k=merge(merge(x,newcode(a)),y);
}
void reverse(int &k,int l,int r){
	split(k,l-1,x,y);
	split(y,r-l+1,y,z);
	rev[y]^=1;
	k=merge(x,merge(y,z));
}
void scan(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		insert(root,i);
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		reverse(root,l,r);
	}
}
void print(int &k){
	if(!k)return;
	if(rev[k])pushdown(k);
	print(child[k][0]);
	printf("%d ",val[k]);
	print(child[k][1]);
}
int main(){
//	freopen("P3391_1.in","r",stdin);
	scan();
	print(root);
	return 0; 
}