sarail @ 2018-04-24 21:03:44

by sarail @ 2018-04-24 21:07:45

//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;
}