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

#define inf 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define fastcall __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline)) 
int n,m,l,r;

  

char buf[MAXN*20], *ptr = buf - 1;
fastcall IL int read(){
    register int x = 0, f = 1, c = *++ptr;
    for(;c>'9'||c<'0';c=*++ptr)if(c=='-')f=-f;
    for(;c>='0'&&c<='9';c=*++ptr)x=x*10+(c^48);
    return x * f;
}

struct node{
    int r,v,s,filp;
    node *ch[2];
      
    void Maintain(){
        s = ch[0]->s + ch[1]->s +1;
    }
  
    void *operator new(size_t);
  
    node(){
        r=0;
        v=0;s=0;
        ch[0]=ch[1]=NULL;
    }
  
    void push_down(){
        if(filp){
            swap(ch[0],ch[1]);
            filp^=1;
            ch[0]->filp^=1;
            ch[1]->filp^=1;
        }
    }
  
    node(int x);
}*null = new node(),*C,*mempool,*root;
  
fastcall IL void* node :: operator new(size_t){
    if(C==mempool){
        C = new node[1<<15];
        mempool = C+(1<<15);
    }
    return C++;
}
  
node :: node(int x){
    v=x;s=1;r=rand();filp=0;
    ch[0]=ch[1]=null;
}
  
typedef pair<node*,node*>pa;
  
fastcall inline pa spilt(node *o,int k){
    if(k==0)return make_pair(null,o);
    if(o==null)return make_pair(null,null);
    o->push_down();
    if(o->ch[0]->s>=k){
        pa y = spilt(o->ch[0],k);
        o->ch[0]=y.second;
        o->Maintain();
        y.second=o;
        return y;
    }
    else{
        pa y = spilt(o->ch[1],k-o->ch[0]->s-1);
        o->ch[1]=y.first;
        o->Maintain();
        y.first=o;
        return y;
    }
}
  
fastcall inline node *merge(node *a,node *b){
    if(a==null)return b;
    if(b==null)return a;
    if(a->r<b->r){
        a->push_down();
        a->ch[1]=merge(a->ch[1],b);
        a->Maintain();
        return a;
    }
    else{
        b->push_down();
        b->ch[0]=merge(a,b->ch[0]);
        b->Maintain();
        return b;
    }
}
  
fastcall IL int Rank(register int x){
    register node *o=root;
    register int ans = 0;
    while(o!=null){
        o->push_down();
        if(x<=o->v)o=o->ch[0];
        else ans+=o->ch[0]->s+1,o=o->ch[1];
    }
    return ans;
}
  
fastcall IL void insert(register int x){
    pa y = spilt(root,Rank(x));
    node *p=new node(x);
    root = merge(merge(y.first,p),y.second);
}
  
fastcall IL void make_filp(register int l,register int r){
    pa x = spilt(root,l-1);
    pa y = spilt(x.second,r-l+1);
    y.first->filp^=1;
    root = merge(x.first,merge(y.first,y.second));
}
  
fastcall inline void dfs(register node *o){
    if(o==null)return;
    o->push_down();
    dfs(o->ch[0]);
    printf("%d ",o->v);
    dfs(o->ch[1]);
}
 
fastcall node* build(register int l,register int r){
    if(l>r)return null;
    register int m = l+r>>1;
    node *p=new node(m);
    p->ch[0]=build(l,m-1);
    p->ch[1]=build(m+1,r);
    p->Maintain();
    return p;
}
 
fastcall IL void erase(register int x){
    register pa o = spilt(root,Rank(x));
    register pa y = spilt(o.second,1);
    delete y.first;
    root = merge(o.first,o.second);
}
 
fastcall IL int kth(register int k){
    register node *o=root;
    while(o!=null){
        if(k==o->ch[0]->s+1)return o->v;
        if(k<=o->ch[0]->s)o=o->ch[0];
        else k-=o->ch[0]->s+1,o=o->ch[1];
    }
}
  
int main(){
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
    fread(buf,1,sizeof(buf),stdin);
    root = null;
    n=read();m=read();
    root=build(1,n);
    while(m--){
        l=read();r=read();
        make_filp(l,r);
    }
    dfs(root);
}