necklace.cpp 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266
  1. #include<stdio.h>
  2. #include<string.h>
  3. const int BLOCKSIZE = 800;
  4. const int MAXL = 500000+10;
  5. const int MAXBLOCK = MAXL/BLOCKSIZE*2+100;
  6. inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}
  7. inline int min(int a,int b){return a<b?a:b;}
  8. int freelist[MAXBLOCK];
  9. int freepos;
  10. inline int newnode(){return freelist[freepos++];}
  11. inline void delnode(int t){freelist[--freepos]=t;}
  12. int data[MAXBLOCK][BLOCKSIZE];
  13. int count[MAXBLOCK];
  14. int account[MAXBLOCK];
  15. int side[MAXBLOCK][2];
  16. int samevalue[MAXBLOCK];
  17. int next[MAXBLOCK];
  18. bool same[MAXBLOCK];
  19. bool reversed[MAXBLOCK];
  20. void reverseblock(int b){
  21. if(b==-1 || !reversed[b])return;
  22. reversed[b]=false;
  23. if(same[b])return;
  24. for(int l=0,r=count[b]-1; l<r; ++l,--r)swap(data[b][l], data[b][r]);
  25. swap(side[b][0], side[b][1]);
  26. }
  27. void maintainblock(int b){
  28. if(count[b]==0)return;
  29. if(same[b]){
  30. account[b]=!!count[b];
  31. side[b][0]=side[b][1]=samevalue[b];
  32. }else{
  33. int *str=data[b];
  34. account[b]=!!count[b];
  35. for(int i=count[b]-1; i>0; --i)if(str[i]!=str[i-1])++account[b];
  36. side[b][0]=str[0];
  37. side[b][1]=str[count[b]-1];
  38. }
  39. }
  40. void maintainlist(int b){
  41. for(; b!=-1; b=next[b])
  42. for(int t=next[b]; t!=-1 && count[b]+count[t]<=BLOCKSIZE; t=next[b]){
  43. if( !(same[b] && same[t] && samevalue[b]==samevalue[t]) ){
  44. reverseblock(b);
  45. reverseblock(t);
  46. if(same[b])for(int i=count[b]-1; i>=0; --i)data[b][i]=samevalue[b];
  47. same[b]=false;
  48. int cb=count[b],*str=data[b];
  49. if(same[t])for(int i=count[t]-1,sv=samevalue[t];i>=0;--i)str[cb+i]=sv;
  50. else for(int i=count[t]-1,*a=data[t];i>=0;--i)str[cb+i]=a[i];
  51. }
  52. count[b]+=count[t];
  53. next[b]=next[t];
  54. delnode(t);
  55. maintainblock(b);
  56. }
  57. }
  58. void find(int &p,int &b){
  59. for(b=0; b!=-1 && p>count[b]; b=next[b])
  60. p-=count[b];
  61. }
  62. void fillblock(int b,int n,int str[],int e){
  63. next[b]=e;
  64. count[b]=n;
  65. memcpy(data[b], str, n*sizeof(int));
  66. same[b]=reversed[b]=false;
  67. maintainblock(b);
  68. }
  69. void fillblock(int b,int n,int v,int e){
  70. next[b]=e;
  71. count[b]=n;
  72. same[b]=true;
  73. samevalue[b]=v;
  74. reversed[b]=false;
  75. maintainblock(b);
  76. }
  77. void splite(int b,int p){
  78. if(b==-1 || count[b]==p)return;
  79. int t=newnode();
  80. reverseblock(b);
  81. if(same[b]) fillblock(t, count[b]-p, samevalue[b], next[b]);
  82. else fillblock(t, count[b]-p, data[b]+p, next[b]);
  83. count[b]=p;
  84. next[b]=t;
  85. maintainblock(b);
  86. }
  87. void insert(int p,int n,int str[]){
  88. int b,t,i;
  89. find(p,b);
  90. splite(b,p);
  91. for(i=0; i + BLOCKSIZE <= n; i+=BLOCKSIZE){
  92. t=newnode();
  93. fillblock(t, BLOCKSIZE, str+i, next[b]);
  94. next[b]=t;
  95. b=t;
  96. }
  97. if(n-i){
  98. t=newnode();
  99. fillblock(t, n-i, str+i, next[b]);
  100. next[b]=t;
  101. }
  102. maintainlist(b);
  103. }
  104. int list[MAXBLOCK];
  105. void reverse(int p,int n){
  106. int b,i,t;
  107. find(p,b);
  108. splite(b,p);
  109. for(i=0,t=next[b]; n>count[t]; n-=count[t],++i,t=next[t])
  110. list[i]=t;
  111. if(n && t!=-1){
  112. splite(t,n);
  113. list[i++]=t;
  114. t=next[t];
  115. }
  116. next[b]=list[--i];
  117. for(; i>=0; --i){
  118. next[list[i]] = i ? list[i-1] : t;
  119. reversed[list[i]] = ! reversed[list[i]];
  120. }
  121. maintainlist(b);
  122. }
  123. void makesame(int p,int n,int v){
  124. int b,t;
  125. find(p,b);
  126. splite(b,p);
  127. for(t=next[b]; t!=-1 && n>count[t];n-=count[t], t=next[t])
  128. fillblock(t, count[t], v, next[t]);
  129. if(n && t!=-1){
  130. splite(t,n);
  131. fillblock(t, n, v, next[t]);
  132. }
  133. maintainlist(b);
  134. }
  135. void listswap(int i,int j){
  136. if(i==j)return;
  137. int bb,be,s1,s2;
  138. find(i,bb);
  139. while(count[bb]==i){bb=next[bb];i=0;}
  140. s1=same[bb] ? samevalue[bb] : reversed[bb] ? data[bb][count[bb]-i-1] : data[bb][i];
  141. find(j,be);
  142. while(count[be]==j){be=next[be];j=0;}
  143. s2=same[be] ? samevalue[be] : reversed[be] ? data[be][count[be]-j-1] : data[be][j];
  144. if(s1==s2)return;
  145. swap(s1,s2);
  146. if(same[bb]){for(int i=count[bb]-1; i>=0; --i)data[bb][i]=samevalue[bb];reversed[bb]=false;}
  147. if(same[be]){for(int i=count[be]-1; i>=0; --i)data[be][i]=samevalue[be];reversed[be]=false;}
  148. same[bb]=same[be]=false;
  149. (reversed[bb] ? data[bb][count[bb]-i-1] : data[bb][i]) = s1;
  150. (reversed[be] ? data[be][count[be]-j-1] : data[be][j]) = s2;
  151. maintainblock(bb);
  152. maintainblock(be);
  153. }
  154. int countsegment(int p,int n){
  155. if(n<=1)return n;
  156. int b;
  157. find(p,b);
  158. while(p==count[b]){b=next[b];p=0;}
  159. int res=1,i,t,l,r,*str=data[b];
  160. --n;
  161. if(!same[b]){
  162. if(reversed[b]){for(i=count[b]-p-1; i>0 && n>0; --i,--n)if(str[i]!=str[i-1])++res;}
  163. else{for(i=p+1; n>0 && i<count[b]; ++i,--n)if(str[i]!=str[i-1])++res;}
  164. }else n-=min(count[b]-p-1, n);
  165. for(t=b; next[t]!=-1 && n>count[next[t]]; t=next[t]){
  166. n -= count[next[t]];
  167. res += account[next[t]];
  168. if(side[t][!reversed[t]] == side[next[t]][reversed[next[t]]])--res;
  169. }
  170. if(n>0){--n;res+=(side[t][!reversed[t]]!=side[next[t]][reversed[next[t]]]);}
  171. t=next[t];str=data[t];
  172. if(!same[t]){
  173. if(reversed[t]){for(i=count[t]-2; i>=0 && n>0; --i,--n)if(str[i]!=str[i+1])++res;}
  174. else{for(i=1; n>0 && i<count[t]; ++i,--n)if(str[i]!=str[i-1])++res;}
  175. }
  176. return res;
  177. }
  178. int tstr[MAXL];
  179. int n,c,q;
  180. void flip(int n){
  181. reverse(1,n-1);
  182. }
  183. void rotate(int k,int n){
  184. reverse(0,n);
  185. reverse(0,k);
  186. reverse(k,n-k);
  187. }
  188. bool same_head_tail(){
  189. int b,t1,t2;
  190. for(b=0; b!=-1 && count[b]==0; b=next[b]);
  191. t1=side[b][reversed[b]];
  192. for(; next[b]!=-1; b=next[b]);
  193. t2=side[b][!reversed[b]];
  194. return t1==t2;
  195. }
  196. int countcircle(){
  197. int res=countsegment(0,n);
  198. if(same_head_tail())--res;
  199. if(res==0)res=1;
  200. return res;
  201. }
  202. void init(){
  203. next[0]=-1;
  204. count[0]=0;
  205. for(int i=1;i<MAXBLOCK;++i)freelist[i]=i;
  206. freepos=1;
  207. freopen("necklace.in","r",stdin);
  208. freopen("necklace.out","w",stdout);
  209. scanf("%d%d",&n,&c);
  210. for(int i=0;i<n;++i)scanf("%d",tstr+i);
  211. insert(0, n, tstr);
  212. }
  213. void solve(){
  214. char order[10];
  215. int k,i,j,x;
  216. scanf("%d",&q);
  217. for(; q; --q){
  218. scanf("%s",order);
  219. switch(order[0]){
  220. case 'R':
  221. scanf("%d",&k);
  222. rotate(k,n);
  223. break;
  224. case 'F':
  225. flip(n);
  226. break;
  227. case 'S':
  228. scanf("%d%d",&i,&j);
  229. listswap(i-1,j-1);
  230. break;
  231. case 'P':
  232. scanf("%d%d%d",&i,&j,&x);
  233. if(j>=i)makesame(i-1, j-i+1, x);
  234. else{
  235. makesame(0, j, x);
  236. makesame(i-1, n-i+1, x);
  237. }
  238. break;
  239. case 'C':
  240. if(order[1]=='S'){
  241. scanf("%d%d",&i,&j);
  242. if(j>=i)printf("%d\n",countsegment(i-1, j-i+1));
  243. else{
  244. int res=countsegment(i-1, n-i+1);
  245. res+=countsegment(0,j);
  246. if(same_head_tail())--res;
  247. printf("%d\n",res);
  248. }
  249. }else printf("%d\n",countcircle());
  250. }
  251. }
  252. fclose(stdin);
  253. fclose(stdout);
  254. }
  255. int main(){
  256. init();
  257. solve();
  258. }