记录编号	455115	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.346 s
提交时间	2017-10-01 13:23:16	内存使用	0.70 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define tp pair <Treap*,Treap*>
#define inf 0x3f3f3f3f
#define size(x) ((x!=NULL)?(x->size):(0))
#define maxl(x) ((x!=NULL)?(x->maxl):(0))
#define maxr(x) ((x!=NULL)?(x->maxr):(0))
#define maxn(x) ((x!=NULL)?(x->maxn):(-inf))
#define sum(x) ((x!=NULL)?(x->sum):(0))

struct Treap{
    Treap* ch[2];
    int key,val,size;
    int rev;
    Treap (int x){
        key=rand();val=x;size=1;rev=0;
        ch[0]=ch[1]=NULL;
    }
    void rever(){
        rev^=1;
        swap(ch[0],ch[1]);
    }
    void pushup(){size=size(ch[0])+size(ch[1])+1;}
    void pushdown(){
        if(rev){
            if(ch[0])ch[0]->rever();
            if(ch[1])ch[1]->rever();
            rev=0;
        }
    }
}*root;

 
void print(Treap *x){
    if(x==NULL)return ;
    x->pushdown();
    if(x->ch[0])print(x->ch[0]);
    printf("%d ",x->val);
    if(x->ch[1])print(x->ch[1]);
}
 
 
Treap* merge(Treap* a,Treap* b){
    if(!a)return b;
    if(!b)return a;
    if(a->key <= b->key){
        a->pushdown();
        a->ch[1]=merge(a->ch[1],b);
        a->pushup(); return a;
    }
    else{
        b->pushdown();
        b->ch[0]=merge(a,b->ch[0]);
        b->pushup(); return b;
    }
}
tp split(Treap* a,int k){
    if(!a)return tp(NULL,NULL);
    a->pushdown();
    tp x;
    if(size(a->ch[0])>=k){
        x=split(a->ch[0],k);
        a->ch[0]=x.second;
        a->pushup();
        x.second=a;
    }
    else{
        x=split(a->ch[1],k-size(a->ch[0])-1);
        a->ch[1]=x.first;
        a->pushup();
        x.first=a;
    }
    return x;
}
 
Treap* s[100050];
Treap* build(int tot){
    Treap *now,*last;
    int top=0;  
    for(int i=1;i<=tot;i++){
        now=new Treap (i);
        last=NULL;
        while(top&&s[top]->key>now->key){
            s[top]->pushup();
            last=s[top--];
        }
        now->ch[0]=last;now->pushup();
        if(top){s[top]->ch[1]=now;s[top]->pushup();}
        s[++top]=now;
    }
    while(top) s[top--]->pushup();
    return s[1];
}

void work_rev(int be,int en){
    tp x=split(root,be-1);
    tp y=split(x.second,en-be+1);
    y.first->rever();
    root=merge(x.first,merge(y.first,y.second));
}
 
 
int n,m;
int main(){
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
    scanf("%d%d",&n,&m);
    root=build(n);
    int be,en;
    while(m--){
        scanf("%d%d",&be,&en);
        work_rev(be,en);
    }
    print(root);
    return 0;
}