```cpp
//emmmm重发一遍
#include<bits/stdc++.h>
using namespace std;
struct node{
int data,sum,tag;
node* ch[2];
int cmp(int x)const{ //k
if(x==(ch[0]->sum+1)) return -1;
return x<(ch[0]->sum+1)?0:1;
}
}*nll=new node(),*root=nll;
int n,m,l,r;
inline void pushdown(node* o){
node* p=o->ch[0];
o->ch[0]=o->ch[1];
o->ch[1]=p;
o->tag=0;
o->ch[0]->tag^=1;
o->ch[1]->tag^=1;
}
inline void maintain(node* o){
o->sum=o->ch[0]->sum+o->ch[1]->sum+1;
}
void rotate(node*& o,int d){
if(o->tag){
pushdown(o);
if(o->ch[d^1]->tag)pushdown(o->ch[d^1]);
//if(o->ch[1]->tag)o->ch[1]->pushdown();
d^=1;
}
node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d];k->ch[d]=o;
maintain(o);maintain(k);
o=k;
}
void insert(node*& o,int x){
if(o==nll){
o=new node();
o->ch[0]=o->ch[1]=nll;
o->data=x-1;
o->tag=0;
}
else {
int d=o->cmp(x);
insert(o->ch[d],x);
}
maintain(o);
}
void splay(node* &o,int k){
if(o->tag)pushdown(o);
int d=o->cmp(k);
if(d==1) k-=o->ch[0]->sum+1;
if(d!=-1){
node* p=o->ch[d];
int d2=p->cmp(k);
int k2= (d2==0? k:k-p->ch[0]->sum-1);
if(d2!= -1){
splay(p->ch[d2],k2);
if(d==d2) rotate(o,d^1);
else rotate(o->ch[d],d);
}
rotate(o,d^1);
}
}
void dfs(node* o){
if(o->tag)pushdown(o);
if(o->ch[0]!=nll) dfs(o->ch[0]);
if(o->data!=0&&o->data!=n+1)
printf("%d ",o->data);
if(o->ch[1]!=nll) dfs(o->ch[1]);
}
int main(){
nll->sum=0;
nll->ch[0]=nll->ch[1]=nll;
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++){
insert(root,i+1);
splay(root,i+1);
}
while(m--){
scanf("%d%d",&l,&r);
splay(root,r+2);
splay(root->ch[0],l);
root->ch[0]->ch[1]->tag^=1;
}
dfs(root);
return 0;
}
```
by sarail @ 2018-04-24 21:07:45