记录编号	432765	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	0.687 s
提交时间	2017-08-03 19:31:27	内存使用	3.19 MiB

#pragma G++ optimize("O3")
#include<cstdio>
#include<iostream>
namespace FIFO
{
    char ch;
	char B[1<<20],*S=B,*T=B;
    #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
    #define isd(c) (c>='0'&&c<='9')
    int aa,bb;int F(){
        while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
        while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return aa;
    }
}
#define gi FIFO::F()
class Troy{
public:
    Troy(){
        for(top;top<siez;top++)
            stk[top]=tree+top;
    }
    void print(){
        dfs(root);
    }
    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);
                }
            }
        }
    }
    inline 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];
        }
    }
    inline 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);
    n=gi,m=gi;
    int l,r;
    war.build(0,n+1);
    for(int i=1;i<=m;i++ ){
        l=gi,r=gi;
        war.change(l,r);        
    }
    war.print();
}