记录编号	423721	评测结果	AAAAAAAAAA
题目名称	2457.[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	0.905 s
提交时间	2017-07-12 14:51:58	内存使用	2.99 MiB

#include<cstdio>
#include<iostream>
inline void read(int &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(!(ch<'0'||ch>'9')){
        x=x*10+ch-48;
        ch=getchar();
    }
}
class Troy{
public:
    Troy(){
        for(top;top<siez;top++)
            stk[top]=tree+top;
    }
    void print(){
        dfs(root);
        printf("\n");
    }
    void build(int l,int r){
        int mid=l+r>>1;
        root=newnode(mid,NULL);
        root->son[0]=build(l,mid-1,root);
        root->son[1]=build(mid+1,r,root);
    }
    void change(int l,int r){
        node *t=find(l);
        splay(t,NULL);
        t=find(r+2);
        splay(t,root);
        root->son[1]->son[0]->lazy^=1;
    }
private:
    struct node{
        int v,size,lazy;
        node *son[2],*f;
    }*root;
    const static int siez=100100;
    node *stk[siez],tree[siez];int top;
    inline node * newnode(int v,node *f){
        node *t=stk[--top];
        t->size=1;
        t->lazy=0;
        t->v=v;
        t->son[1]=t->son[0]=NULL;
        t->f=f;
        return t;
    }
    node *build (int l,int r,node *f){
        if(l>r) return NULL;
        int mid=l+r>>1;
        node *t=newnode(mid,f);
        t->son[0]=build(l,mid-1,t);
        t->son[1]=build(mid+1,r,t);
        return update(t),t;
    }
    inline int size(node *t){
        return t==NULL ?0:t->size;
    }
    inline void  update(node *t){
        t->size=1+size(t->son[0])+size(t->son[1]);
    }
    void updown(node *t){
        if(t!=NULL){
            std::swap(t->son[0],t->son[1]);
            if(t->son[0]!=NULL)
            t->son[0]->lazy^=1;
            if(t->son[1]!=NULL)
            t->son[1]->lazy^=1;
            t->lazy=0;
        }
    }
    inline bool son(node* f,node* s){
        if(f==NULL) return 0;
        return f->son[1]==s;
    }
    inline void connect(node *f,node *s,bool k){
        if(f!=NULL) f->son[k]=s;
        else    root=s;
        if(s!=NULL) s->f=f;
    }
    inline void rotate(node* t){
        node *f=t->f,*g=f->f;
        bool a=son(f,t),b=!a;
        connect(f,t->son[b],a);
        connect(g,t,son(g,f));
        connect(t,f,b);
        update(f);
        update(t);
    }
    inline  void splay(node *t,node *p){
        if(t){
            while(t->f!=p){
                node *f =t->f,*g=f->f;
                if(g==p)    rotate(t);
                else{
                    if(son(g,f)^son(f,t))
                        rotate(t),rotate(t);
                    else
                        rotate(f),rotate(t);
                }
            }
        }
    }
    node *find(int kth){
        for(node *now=root;;){
            if(now->lazy){
                updown(now);
            }
            if(kth>size(now->son[0])){
                kth-=size(now->son[0]);
                if(kth==1)  return now;
                else    now=now->son[1],kth--;
            }
            else   
                now=now->son[0];
        }
    }
    void dfs(node *t){
        if(t->lazy){
            updown(t);
        }  
        if(t->son[0]!=NULL)
            dfs(t->son[0]);
        if(t->v!=0&&t->v!=size(root)-1)
              printf("%d ",t->v);
        if(t->son[1]!=NULL)
            dfs(t->son[1]);
    }
}war;
int n,m;
int main(){
    freopen("sph.in","r",stdin);
    freopen("sph.out","w",stdout);
    read(n),read(m);
    int l,r;
    war.build(0,n+1);
    for(int i=1;i<=m;i++ ){
        read(l),read(r);
        war.change(l,r);    
     //   war.print();       
    }
    war.print();
  //  while(1);
}