1 2 #include <iostream> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cstring> 6 #include <cstdlib> 7 8 using namespace std; 9 struct node 10 { 11 int data; 12 int left; 13 int right; 14 int key; 15 int size; 16 bool turn; 17 int ans; 18 int mark; 19 node* ls,*rs; 20 node(int dat=0,int ke=0) 21 { 22 data=dat; 23 key=ke; 24 left=data; 25 right=data; 26 size=1; 27 turn=false; 28 mark=0; 29 ans=1; 30 ls=NULL; 31 rs=NULL; 32 } 33 }no[500010]; 34 35 36 void pushdown(node* now) 37 { 38 if (now->mark) 39 { 40 if (now->ls) 41 { 42 now->ls->data=now->mark; 43 now->ls->mark=now->mark; 44 now->ls->left=now->mark; 45 now->ls->right=now->mark; 46 now->ls->ans=1; 47 } 48 if (now->rs) 49 { 50 now->rs->data=now->mark; 51 now->rs->mark=now->mark; 52 now->rs->left=now->mark; 53 now->rs->right=now->mark; 54 now->rs->ans=1; 55 } 56 now->mark=0; 57 } 58 if (now->turn) 59 { 60 node* l=now->ls; 61 node* r=now->rs; 62 if (now->ls) 63 now->ls->left^=now->ls->right^=now->ls->left^=now->ls->right; 64 if (now->rs) 65 now->rs->left^=now->rs->right^=now->rs->left^=now->rs->right; 66 now->ls=r; 67 now->rs=l; 68 if (now->ls) now->ls->turn=!now->ls->turn; 69 if (now->rs) now->rs->turn=!now->rs->turn; 70 now->turn=false; 71 } 72 } 73 74 void update(node* now) 75 { 76 now->size=1; 77 now->ans=1; 78 now->left=now->data; 79 now->right=now->data; 80 if (now->ls) 81 { 82 now->size+=now->ls->size; 83 now->ans+=now->ls->ans; 84 now->left=now->ls->left; 85 } 86 if (now->rs) 87 { 88 now->size+=now->rs->size; 89 now->ans+=now->rs->ans; 90 now->right=now->rs->right; 91 } 92 if (now->ls) 93 if (now->ls->right==now->data) now->ans--; 94 if (now->rs) 95 if (now->rs->left==now->data) now->ans--; 96 } 97 98 node* merge(node* a,node* b) 99 { 100 if (!b) return a; 101 if (!a) return b; 102 pushdown(a); 103 pushdown(b); 104 if (a->key<=b->key) 105 { 106 a->rs=merge(a->rs,b); 107 update(a); 108 return a; 109 } 110 else 111 { 112 b->ls=merge(a,b->ls); 113 update(b); 114 return b; 115 } 116 } 117 118 struct npair 119 { 120 node* l,*r; 121 npair(node* a,node* b) 122 { 123 l=a; 124 r=b; 125 } 126 }; 127 128 npair split(node* a,int k) 129 { 130 if (!a) return npair(NULL,NULL); 131 if (k==0) return npair(NULL,a); 132 pushdown(a); 133 if (a->ls) 134 { 135 if (a->ls->size>=k) 136 { 137 npair km=split(a->ls,k); 138 a->ls=km.r; 139 update(a); 140 return npair(km.l,a); 141 } 142 else 143 { 144 npair km=split(a->rs,k-a->ls->size-1); 145 a->rs=km.l; 146 update(a); 147 return npair(a,km.r); 148 } 149 } 150 else 151 { 152 npair km=split(a->rs,k-1); 153 a->rs=km.l; 154 update(a); 155 return npair(a,km.r); 156 } 157 } 158 node* insert(node* root,node* newnode) 159 { 160 return merge(root,newnode); 161 } 162 163 void turn(node* now) 164 { 165 now->turn=!now->turn; 166 now->left^=now->right^=now->left^=now->right; 167 } 168 169 node* rotate(node* root,int num) 170 { 171 int n=root->size; 172 num=num%n; 173 int k=n-num; 174 npair km = split(root,k); 175 return merge(km.r,km.l); 176 } 177 178 node* flip(node* root) 179 { 180 int n=root->size; 181 int r; 182 if (n%2==1) 183 { 184 r=n/2+1; 185 } 186 else 187 { 188 r=n/2; 189 } 190 npair km=split(root,r); 191 npair km2=split(km.l,1); 192 if (n%2==1) 193 { 194 turn(km2.r); 195 turn(km.r); 196 return merge(merge(km2.l,km.r),km2.r); 197 } 198 else 199 { 200 npair km3=split(km.r,1); 201 turn(km2.r); 202 turn(km3.r); 203 return merge(merge(km2.l,km3.r),merge(km3.l,km2.r)); 204 } 205 } 206 207 node* swap(node* root,int i,int j) 208 { 209 if (i>j) i^=j^=i^=j; 210 if (i==j) return root; 211 npair km=split(root,i); 212 npair km2=split(km.l,i-1); 213 npair km3=split(km.r,j-i); 214 npair km4=split(km3.l,j-i-1); 215 return merge(merge(merge(km2.l,km4.r),km4.l),merge(km2.r,km3.r)); 216 } 217 218 node* paint(node* root,int i,int j,int x) 219 { 220 int n=root->size; 221 if (i<=j) 222 { 223 npair km=split(root,i-1); 224 npair km2=split(km.r,j-i+1); 225 km2.l->mark=x; 226 km2.l->data=x; 227 km2.l->ans=1; 228 km2.l->left=x; 229 km2.l->right=x; 230 return merge(km.l,merge(km2.l,km2.r)); 231 } 232 else 233 { 234 npair km=split(root,j); 235 int nn=km.r->size; 236 npair km2=split(km.r,nn-n+i-1); 237 km.l->mark=x; 238 km.l->data=x; 239 km.l->ans=1; 240 km.l->left=x; 241 km.l->right=x; 242 km2.r->mark=x; 243 km2.r->data=x; 244 km2.r->ans=1; 245 km2.r->left=x; 246 km2.r->right=x; 247 return merge(km.l,merge(km2.l,km2.r)); 248 } 249 } 250 251 node* root; 252 int countS(int i,int j) 253 { 254 int n=root->size; 255 if (i<=j) 256 { 257 npair km=split(root,i-1); 258 npair km2=split(km.r,j-i+1); 259 int ret=km2.l->ans; 260 root=merge(km.l,merge(km2.l,km2.r)); 261 return ret; 262 } 263 else 264 { 265 npair km=split(root,j); 266 int nn=km.r->size; 267 npair km2=split(km.r,nn-n+i-1); 268 int ret=km.l->ans+km2.r->ans; 269 if (km.l->left==km2.r->right) ret--; 270 root=merge(km.l,merge(km2.l,km2.r)); 271 return ret; 272 } 273 } 274 275 int count() 276 { 277 int ret=root->ans; 278 if (root->left==root->right&&ret!=1) ret--; 279 return ret; 280 } 281 282 void print(node* now,bool b) 283 { 284 if (!now) return; 285 b=b^now->turn; 286 // if (!b) 287 print(now->ls,b); 288 // else 289 // print(now->rs,b); 290 printf("data: %d size: %d mark: %d turn: %d ans: %d left: %d right: %d ",now->data,now->size,now->mark,now->turn,now->ans,now->left,now->right); 291 // if (!b) 292 print(now->rs,b); 293 // else 294 // print(now->ls,b); 295 } 296 297 void print(node* now) 298 { 299 if (!now) return; 300 pushdown(now); 301 print(now->ls); 302 printf("%d ",now->data); 303 print(now->rs); 304 } 305 306 int cnt=-1; 307 int main() 308 { 309 int n,c; 310 scanf("%d%d",&n,&c); 311 int j; 312 for (int i=1;i<=n;++i) 313 { 314 scanf("%d",&j); 315 node* q=&no[++cnt]; 316 *q=node(j,rand()); 317 root=insert(root,q); 318 } 319 int m; 320 scanf("%d",&m); 321 char cmd[3]; 322 int l,r,k; 323 for (int i=1;i<=m;++i) 324 { 325 scanf("%s",cmd); 326 if (cmd[0]=='R'){scanf("%d",&k);root=rotate(root,k);} 327 if (cmd[0]=='F'){root=flip(root);} 328 if (cmd[0]=='S'){scanf("%d%d",&l,&r);root=swap(root,l,r);} 329 if (cmd[0]=='P'){scanf("%d%d%d",&l,&r,&k);root=paint(root,l,r,k);} 330 if (cmd[0]=='C'&&cmd[1]!='S'){printf("%d ",count());} 331 if (cmd[0]=='C'&&cmd[1]=='S'){scanf("%d%d",&l,&r);printf("%d ",countS(l,r));} 332 // printf("%d ",i); 333 // printf("-------------------- "); 334 // print(root,false); 335 // printf("-------------------- "); 336 } 337 return 0; 338 }