hh

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<cmath>  5 #include<algorithm>  6 #include<cstdlib>  7 #include<ctime>  8 using namespace std;  9 const int MAXN=300001; 10 static void read(int &n) 11 { 12     char c=‘+‘;int x=0;bool flag=0; 13     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;} 14     while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c-48);c=getchar();} 15     flag==1?n=-x:n=x; 16 } 17 int ch[MAXN][3];// 0左孩子 1右孩子 18 int val[MAXN];// 每一个点的权值 19 int pri[MAXN];// 随机生成的附件权值 20 int siz[MAXN];// 以i为节点的树的节点数量 21 int sz;// 总结点的数量  22 int n,m; 23 int x,y,z,a,b,root; 24 int mark[MAXN]; 25 void update(int x) 26 { 27     siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]]; 28 }  29 void pushdown(int x) 30 { 31     if(x&&mark[x]) 32     { 33         mark[x]=0; 34         swap(ch[x][0],ch[x][1]); 35         if(ch[x][0])    mark[ch[x][0]]^=1; 36         if(ch[x][1])    mark[ch[x][1]]^=1; 37     } 38 } 39 int new_node(int v) 40 { 41     siz[++sz]=1;// 新开辟一个节点 42     val[sz]=v; 43     pri[sz]=rand();  44     return sz; 45 } 46  47 int merge(int x,int y)// 合并  48 { 49     if(!x||!y)    return x+y;// x和y中必定有一个是0 50     pushdown(x);pushdown(y); 51     if(pri[x]<pri[y])// 把x加到左边的树上  52     { 53         ch[x][1]=merge(ch[x][1],y);// 不懂的看GIF图  54         update(x); 55         return x; 56     }  57     else 58     { 59         ch[y][0]=merge(x,ch[y][0]); 60         update(y); 61         return y; 62     } 63 } 64 void split(int now,int k,int &x,int &y) 65 { 66     if(!now) x=y=0;// 到达叶子节点 67     else 68     { 69         pushdown(now); 70         if (k<=siz[ch[now][0]]) 71             y=now,split(ch[now][0],k,x,ch[now][0]); 72         else 73             x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y); 74         update(now); 75     }  76 } 77 int build(int l,int r) 78 { 79     if(l>r)    return 0; 80     int mid=(l+r)>>1;int v=mid-1; 81     int now=new_node(v); 82     ch[now][0]=build(l,mid-1); 83     ch[now][1]=build(mid+1,r); 84     update(now); 85     //pushdown(now); 86     return now; 87 } 88 void dfs(int x) 89 { 90     if(!x)    return ; 91     pushdown(x); 92     dfs(ch[x][0]); 93     if(val[x]>=1&&val[x]<=n) 94         printf("%d ",val[x]); 95     dfs(ch[x][1]); 96 } 97 void res(int l,int r) 98 { 99     int a,b,c,d;100     split(root,r+1,a,b);101     split(a,l,c,d);102     mark[d]^=1;103     root=merge(merge(c,d),b);104 }105 int main()106 {107     srand((unsigned)time(NULL));108     109     read(n);read(m);110     root=build(1,n+2);111     for(int i=1;i<=m;i++)112     {int l,r;read(l);read(r);res(l,r);}113     dfs(root);114     return 0;115 }