fork download
  1. const
  2. fi = '';
  3. var
  4. a : array[1..50000] of longint;
  5. val,valmax,rem : array[1..200000] of longint;
  6. n,k,m : longint;
  7.  
  8.  
  9. procedure enter;
  10. var
  11. i,j,tmp : longint;
  12. begin
  13. n := 0;
  14. readln(k,m);
  15. i := 1;
  16. for j := 1 to k do
  17. begin
  18. read(tmp);
  19. a[i] := 1;
  20. inc(i,tmp);
  21. inc(n,tmp);
  22. end;
  23. readln;
  24. end;
  25.  
  26. procedure init(s,l,r : longint);
  27. var
  28. mid : longint;
  29. begin
  30. if l = r then
  31. begin
  32. valmax[s] := 1;
  33. exit;
  34. end;
  35. mid := (l + r) div 2;
  36. init(2*s,l,mid);
  37. init(2*s+1,mid+1,r);
  38. valmax[s] := valmax[2*s] + valmax[2*s+1];
  39. end;
  40.  
  41. procedure init2(s,l,r : longint);
  42. var
  43. mid : longint;
  44. begin
  45. if l = r then
  46. begin
  47. inc(val[s],a[l]);
  48. exit;
  49. end;
  50. mid := (l + r) div 2;
  51. init2(2*s,l,mid);
  52. init2(2*s+1,mid+1,r);
  53. val[s] := val[2*s] + val[2*s+1];
  54. end;
  55.  
  56. procedure trans(s,l,r : longint);
  57. var
  58. mid : longint;
  59. begin
  60. if (s = 0) or (l = r) then exit;
  61. mid := (l + r) div 2;
  62. inc(val[2*s],rem[s]*(mid-l+1));
  63. inc(val[2*s+1],rem[s]*(r-mid));
  64. inc(rem[2*s],rem[s]);
  65. inc(rem[2*s+1],rem[s]);
  66. rem[s] := 0;
  67. end;
  68.  
  69. procedure Jupdate(s,l,r,u,v : longint);
  70. var
  71. mid : longint;
  72. begin
  73. if (r < u) or (v < l) then exit;
  74. if (u <= l) and (r <= v) then
  75. begin
  76. if val[s] = valmax[s] then
  77. begin
  78. dec(val[s],r-l+1);
  79. dec(rem[s]);
  80. exit;
  81. end;
  82. if val[s] = 0 then exit;
  83. end;
  84. trans(s,l,r);
  85. mid := (l + r) div 2;
  86. Jupdate(2*s,l,mid,u,v);
  87. Jupdate(2*s+1,mid+1,r,u,v);
  88. val[s] := val[2*s] + val[2*s+1];
  89. end;
  90.  
  91. procedure Dupdate(s,l,r,u,v : longint);
  92. var
  93. mid : longint;
  94. begin
  95. if (r < u) or (v < l) then exit;
  96. if (u <= l) and (r <= v) then
  97. begin
  98. if val[s] = 0 then
  99. begin
  100. inc(val[s],r-l+1);
  101. inc(rem[s]);
  102. exit;
  103. end;
  104. if val[s] = valmax[s] then exit;
  105. end;
  106. trans(s,l,r);
  107. mid := (l + r) div 2;
  108. Dupdate(2*s,l,mid,u,v);
  109. Dupdate(2*s+1,mid+1,r,u,v);
  110. val[s] := val[2*s] + val[2*s+1];
  111. end;
  112.  
  113. procedure query(c : char; u,v : longint);
  114. begin
  115. if c = 'J' then Jupdate(1,1,n,u+1,v)
  116. else Dupdate(1,1,n,u+1,v);
  117. end;
  118.  
  119. procedure main;
  120. var
  121. i,u,v : longint;
  122. c : char;
  123. begin
  124. init(1,1,n);
  125. init2(1,1,n);
  126. for i := 1 to m do
  127. begin
  128. read(c);
  129. if c = 'C' then
  130. begin
  131. writeln(val[1]);
  132. readln;
  133. end
  134. else
  135. begin
  136. readln(u,v);
  137. query(c,u,v);
  138. end;
  139. end;
  140. end;
  141.  
  142.  
  143. begin
  144. assign(input,fi);
  145. reset(input);
  146. enter;
  147. main;
  148. close(input);
  149. end.
  150.  
Success #stdin #stdout 0s 2768KB
stdin
2 3
2 2
J 2 3
D 2 4
C
stdout
3