题意：给你一个字符串str ,从1 开始长度为s，每次给你一个 a[i] ，然后将 [ a[i] , (s-a[i]+1) ] 翻转，问你经过n次操作以后整个字符串是什么样的。
解题思路：
1）根据负负得正的思路，我们只需要从内到外，看那些区域需要翻转，那些区域不需要就行了。
解题代码：
1 // File Name: b.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月27日 星期五 00时33分41秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 200005 26 using namespace std; 27 char str[maxn]; 28 int a[maxn]; 29 int cmp(int a, int b) 30 { 31 return a > b; 32 } 33 int n; 34 void change(int l , int r) 35 { 36 for(int i = l ;i <= r ;i ++) 37 { 38 swap(str[i],str[n-i+1]); 39 } 40 } 41 int main(){ 42 scanf("%s",&str[1]); 43 int m ; 44 n = strlen(&str[1]); 45 scanf("%d",&m); 46 for(int i = 1;i <= m; i ++) 47 scanf("%d",&a[i]); 48 sort(a+1,a+1+m,cmp); 49 int last = n/2; 50 for(int i = 1; i <= m;i ++) 51 { 52 if((m - i) % 2 == 0) 53 { 54 change(a[i],last); 55 } 56 last = a[i] - 1; 57 } 58 puts(&str[1]); 59 return 0; 60 }
2）splay ，我们知道，splay翻转序列只需要logn 所以splay也可以解 .(想法来源是来自于湖大glqAC，被这天大的脑洞吓到了)
1 // File Name: cf525b.cpp 2 // Author: darkdream 3 // Created Time: 2015年04月03日 星期五 22时48分43秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 const int maxn = 200005; 28 struct SplayTree{ 29 int sz[maxn]; 30 int ch[maxn][2]; 31 int pre[maxn]; 32 int n ; 33 int rev[maxn]; 34 int root ,top1,top2; 35 int ss[maxn],que[maxn]; 36 37 inline void Rotate(int x,int f){ 38 int y = pre[x]; 39 push_down(y); 40 push_down(x); 41 ch[y][!f] = ch[x][f]; 42 pre[ch[x][f]] = y ; 43 pre[x] = pre[y]; 44 if(pre[x]) ch[pre[y]][ch[pre[y]][1] == y] = x; 45 ch[x][f] = y ; 46 pre[y] = x ; 47 push_up(y); 48 } 49 inline void Splay(int x, int goal){ 50 push_down(x); 51 while(pre[x] != goal){ 52 if(pre[pre[x]] == goal){ 53 Rotate(x, ch[pre[x]][0] == x); 54 }else{ 55 int y = pre[x],z = pre[y]; 56 int f = (ch[z][0] == y); 57 if(ch[y][f] == x){ 58 Rotate(x,!f) , Rotate(x,f); 59 }else{ 60 Rotate(y,f) , Rotate(x,f); 61 } 62 } 63 } 64 push_up(x); 65 if(goal == 0) root = x; 66 } 67 inline void RotateTo(int k ,int goal){ 68 int x = root; 69 push_down(x); 70 while(sz[ch[x][0]] != k ){ 71 if(k < sz[ ch[x][0] ]){ 72 x = ch[x][0]; 73 }else{ 74 k -= (sz[ch[x][0]] + 1); 75 x = ch[x][1]; 76 } 77 push_down(x); 78 } 79 Splay(x,goal); 80 } 81 inline void erase(int x){ 82 int father = pre[x]; 83 int head = 0 , tail = 0 ; 84 for(que[tail ++] = x ; head < tail ;head ++){ 85 ss[top2++] = que[head]; 86 if(ch[que[head] ][0]) que[tail ++] = ch[que[head]][0]; 87 if(ch[que[head] ][1]) que[tail ++] = ch[que[head]][1]; 88 } 89 ch[father][ch[father][1] == x] = 0 ; 90 push_up(father); 91 } 92 inline void NewNode(int &x,char c){ 93 if(top2) x = ss[--top2]; 94 else x = ++top1; 95 ch[x][0] = ch[x][1] = pre[x] = 0 ; 96 sz[x] = 1; 97 rev[x] = 0; 98 val[x] = c; 99 } 100 inline void push_down(int x){ 101 if(rev[x]) 102 { 103 swap(ch[x][0],ch[x][1]); 104 rev[ch[x][0]] ^= 1 ; 105 rev[ch[x][1]] ^= 1 ; 106 rev[x] = 0 ; 107 } 108 } 109 inline void push_up(int x){ 110 sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]]; 111 } 112 inline void makeTree(int &x,int l ,int r,int f){ 113 if(l > r) return ; 114 int m = (l + r ) >> 1; 115 NewNode(x,str[m]); 116 makeTree(ch[x][0],l,m-1,x); 117 makeTree(ch[x][1],m+1,r,x); 118 pre[x] = f; 119 push_up(x); 120 } 121 inline void init(){ 122 ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0 ; 123 mx[0] = 0 ; 124 root = top1 = 0 ; 125 NewNode(root,' '); 126 NewNode(ch[root][1],' '); 127 pre[top1] = root; 128 sz[root] = 2; 129 // printf("%d*** ",mx[root]); 130 131 scanf("%s",&str[1]); 132 n = strlen(&str[1]); 133 makeTree(ch[ch[root][1]][0],1,n,ch[root][1]); 134 push_up(ch[root][1]); 135 push_up(root); 136 137 } 138 void print(int x) 139 { 140 if(x == 0 ) 141 return; 142 push_down(x); 143 print(ch[x][0]); 144 printf("%c",val[x]); 145 print(ch[x][1]); 146 } 147 inline void update(int l ,int r){ 148 RotateTo(l-1,0); 149 RotateTo(r+1,root); 150 rev[ch[ch[root][1]][0]] ^= 1; 151 //Splay(ch[ch[root][1]][0],0); 152 } 153 inline void query(){ 154 RotateTo(0,0); 155 RotateTo(n+1,root); 156 //print(ch[ch[root][1]][0]); 157 print(ch[ch[root][1]][0]); 158 } 159 char str[maxn]; 160 char val[maxn]; 161 int mx[maxn]; 162 }spt; 163 int ta,tb; 164 int n , q; 165 int main(){ 166 spt.init(); 167 //spt.query(); 168 scanf("%d",&q); 169 for(int i = 1;i <= q; i++) 170 { 171 scanf("%d",&ta); 172 spt.update(ta,spt.n-ta+1) ; 173 } 174 spt.query(); 175 return 0; 176 }