sequence.cpp 5.5 KB

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