题意：对序列取出连续的一段接到剩下的第k个值后面，或者把一段序列反转。
解题思路：splay 区间操作。
解题代码：
1 // File Name: hdu3487.cpp 2 // Author: darkdream 3 // Created Time: 2015年04月09日 星期四 10时16分12秒 4 5 #include 6 #include 7 #include 8 #include<set> 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #define LL long long 25 #define maxn 310000 26 using namespace std; 27 28 char str[10]; 29 int ta,tb,tc; 30 int n , m ; 31 int lastans[maxn]; 32 struct SplayTree{ 33 int sz[maxn]; 34 int ch[maxn][2]; 35 int pre[maxn]; 36 int root ,top1,top2; 37 int ss[maxn],que[maxn]; 38 int rev[maxn]; 39 inline void Rotate(int x, int f){ 40 int y = pre[x]; 41 push_down(y); 42 push_down(x); 43 ch[y][!f] = ch[x][f]; 44 pre[ch[x][f]] = y ; 45 pre[x] = pre[y]; 46 if(pre[x]) ch[pre[y]][ch[pre[y]][1] == y] = x; 47 ch[x][f] = y; 48 pre[y] = x; 49 push_up(y); 50 } 51 inline void Splay(int x, int goal){ 52 push_down(x); 53 while(pre[x] != goal){ 54 if(pre[pre[x]] == goal){ 55 Rotate(x,ch[pre[x]][0] == x); 56 }else{ 57 int y = pre[x],z = pre[y]; 58 int f = (ch[z][0] == y); 59 if(ch[y][f] == y ){ 60 Rotate(x,!f),Rotate(x,f); 61 }else{ 62 Rotate(y,f),Rotate(x,f); 63 } 64 } 65 } 66 push_up(x); 67 if(goal == 0 ) root = x; 68 } 69 inline void RotateTo(int k ,int goal){ 70 int x = root ; 71 push_down(x); 72 while(sz[ch[x][0]] != k ){ 73 if(k 0]]){ 74 x = ch[x][0]; 75 }else{ 76 k -= (sz[ch[x][0]] +1) ; 77 x = ch[x][1]; 78 } 79 push_down(x); 80 } 81 Splay(x,goal); 82 } 83 inline void NewNode(int &x ,int c){ 84 if(top2) x = ss[--top2]; 85 else x = ++ top1; 86 ch[x][0] = ch[x][1] = pre[x] = 0 ; 87 sz[x] = 1; 88 89 val[x] = c ; 90 rev[x] = 0 ; 91 92 } 93 inline void push_down(int x){ 94 if(rev[x]) 95 { 96 swap(ch[x][0],ch[x][1]); 97 rev[ch[x][0]] ^= 1; 98 rev[ch[x][1]] ^= 1; 99 rev[x] = 0 ; 100 } 101 } 102 inline void push_up(int x){ 103 sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]]; 104 } 105 inline void makeTree(int &x, int l ,int r ,int f){ 106 if(l > r) return ; 107 int m = (l + r) >> 1; 108 NewNode(x, m); 109 makeTree(ch[x][0] , l , m-1, x); 110 makeTree(ch[x][1] , m+1 , r, x); 111 pre[x] = f; 112 push_up(x); 113 } 114 inline void init(int n){ 115 rev[0] = ch[0][1] = ch[0][0] = pre[0] = sz[0] = 0 ; 116 root = top1 =0 ; 117 NewNode(root,-1); 118 NewNode(ch[root][1],-1); 119 pre[ch[root][1]] = root ; 120 sz[root] = 2; 121 122 makeTree(ch[ch[root][1]][0],1,n,ch[root][1]); 123 push_up(ch[root][1]); 124 push_up(root); 125 } 126 inline void cut(int l,int r, int si){ 127 128 RotateTo(l-1,0); 129 RotateTo(r+1,root); 130 131 int del = ch[ch[root][1]][0]; 132 ch[ch[root][1]][0] = 0 ; 133 push_up(ch[root][1]); 134 push_up(root); 135 RotateTo(si,0); 136 RotateTo(si+1,root); 137 pre[del] = ch[root][1]; 138 ch[ch[root][1]][0] = del ; 139 Splay(ch[ch[root][1]][0],0); 140 //push_up(ch[root][1]); 141 //push_up(root); 142 } 143 inline void flip(int l , int r ) 144 { 145 RotateTo(l-1,0); 146 RotateTo(r+1,root); 147 rev[ch[ch[root][1]][0]] ^= 1; 148 Splay(ch[ch[root][1]][0],0); 149 } 150 void print(int x,int k ){ 151 if(x == 0 ) 152 return; 153 push_down(x); 154 print(ch[x][0],k); 155 lastans[k+sz[ch[x][0]]] = val[x]; 156 print(ch[x][1],k+1+sz[ch[x][0]]); 157 } 158 int val[maxn]; 159 160 }spt; 161 int main(){ 162 while(scanf("%d %d",&n,&m) != EOF) 163 { 164 if(n == -1) 165 break; 166 spt.init(n); 167 for(int i = 1;i <= m;i ++) 168 { 169 scanf("%s",str); 170 if(str[0] == ‘C‘) 171 { 172 scanf("%d %d %d",&ta,&tb,&tc); 173 spt.cut(ta,tb,tc); 174 }else{ 175 scanf("%d %d",&ta,&tb); 176 spt.flip(ta,tb); 177 } 178 } 179 spt.print(spt.root,0); 180 for(int i = 1;i <= n; i ++) 181 printf(i == 1?"%d":" %d",lastans[i]); 182 printf("\n"); 183 } 184 return 0; 185 }
HDU 3487 Play with Chain
京公网安备 11010802041100号