codevs3243 区间翻转

题目描述 Description

给出N个数，要求做M次区间翻转（如1 2 3 4变成4 3 2 1），求出最后的序列

输入描述 Input Description

第一行一个数N，下一行N个数表示原始序列，在下一行一个数M表示M次翻转，之后的M行每行两个数L，R表示将区间[L,R]翻转。

输出描述 Output Description

一行N个数，表示最终序列。

样例输入 Sample Input

1 2 3 4

1 2

3 4

样例输出 Sample Output

2 1 4 3

数据范围及提示 Data Size & Hint

对于30%的数据满足n<=100 , m <= 10000

对于100%的数据满足n <= 150000 , m <= 150000

对于100%的数据满足n为2的幂，且L = i * 2^j + 1 , R = (i + 1) * 2^j

正解：splay

解题报告：

　　一样的区间翻转，只是我只翻转位置编号，最后对着序列输出就可以了。

  1 //It is made by jump~
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <ctime>
  9 #include <vector>
 10 #include <queue>
 11 #include <map>
 12 #include <set>
 13 #ifdef WIN32   
 14 #define OT "%I64d"
 15 #else
 16 #define OT "%lld"
 17 #endif
 18 using namespace std;
 19 typedef long long LL;
 20 const int MAXN = 150011;
 21 int n,m;
 22 int id[MAXN];
 23 int fa[MAXN],c[MAXN][2],size[MAXN];
 24 int tag[MAXN];
 25 int rt;
 26 //splay的有序按照位置有序，结点存储的是值
 27 
 28 inline int getint()
 29 {
 30        int w=0,q=0;
 31        char c=getchar();
 32        while((c<'0' || c>'9') && c!='-') c=getchar();
 33        if (c=='-')  q=1, c=getchar();
 34        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();
 35        return q ? -w : w;
 36 }
 37 
 38 inline void update(int now){
 39     int l=c[now][0],r=c[now][1];
 40     size[now]=size[l]+size[r]+1;
 41 }
 42 
 43 inline void pushdown(int now){   
 44     if(tag[now]) {
 45     swap(c[now][0],c[now][1]);//交换，画个图就可以知道
 46     tag[c[now][0]]^=1; tag[c[now][1]]^=1;//标记改变
 47     tag[now]=0;
 48     }
 49 }
 50 
 51 inline void build(int l,int r,int f){
 52     if(l>r) return ;
 53     if(l==r) {
 54     size[l]=1; fa[l]=f;
 55     if(l<f) c[f][0]=l;
 56     else c[f][1]=l;
 57     return ;
 58     }
 59     int mid=(l+r)/2; build(l,mid-1,mid); build(mid+1,r,mid);
 60     fa[mid]=f; if(mid<f) c[f][0]=mid; else c[f][1]=mid;
 61     update(mid);
 62 }
 63 
 64 inline void rotate(int x,int &k){
 65     int y=fa[x],z=fa[y];  int l,r;
 66     if(x==c[y][0]) l=0; else l=1; 
 67     r=l^1;
 68     if(y==k) k=x;
 69     else {
 70     if(c[z][0]==y) c[z][0]=x; 
 71     else c[z][1]=x;
 72     }
 73     fa[x]=z;  fa[y]=x;
 74     fa[c[x][r]]=y; c[y][l]=c[x][r];
 75     c[x][r]=y;
 76     update(y); update(x);//z不需要！！！
 77 }
 78 
 79 inline void splay(int x,int &k){//把x旋到k
 80     int y,z;
 81     while(x!=k) {
 82     y=fa[x]; z=fa[y];
 83     if(y!=k) {
 84         if(c[y][0]==x ^ c[z][0]==y) rotate(x,k);//在不同边时，旋x
 85         else rotate(y,k);//相同边时，旋y
 86     }
 87     rotate(x,k);
 88     }
 89 }
 90 
 91 inline int find(int x,int rank){
 92     pushdown(x);//每次做之前，下传标记
 93     int l=c[x][0],r=c[x][1];
 94     if(size[l]+1==rank) return x;
 95     else if(size[l]>=rank) return find(l,rank);
 96     else return find(r,rank-size[l]-1);//还要减掉根结点那一个点
 97 }
 98 
 99 inline void work(int l,int r){
100     int zuo=find(rt,l),you=find(rt,r+2);//找到与这个区间相邻的两个结点
101     splay(zuo,rt); splay(you,c[rt][1]);//把左相邻结点旋到根，右相邻结点旋到根的右子树，则右相邻结点的左子树即所求区间
102     tag[c[you][0]]^=1;
103 }
104 
105 inline void solve(){
106     n=getint(); 
107     for(int i=1;i<=n;i++) id[i]=getint();
108     build(1,n+2,0);//加两个虚拟结点
109     rt=(n+3)/2;
110 
111     int l,r;
112     m=getint();
113     for(int i=1;i<=m;i++) {
114     l=getint(),r=getint();
115     work(l,r);
116     }
117     for(int i=2;i<=n+1;i++) {
118     printf("%d ",id[find(rt,i)-1]);
119     }
120 }
121 
122 int main()
123 {
124   solve();
125   return 0;
126 }