chang2394

Untitled

Sep 21st, 2014
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.37 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #define MAXH 20 // 1+ceil(log2(400001))
  4. typedef long long ll;
  5. ll memosum[600001];
  6. ll sum(ll n)
  7. {
  8. if(n==0)
  9. return 0;
  10. if(memosum[n]!=0)
  11. return memosum[n];
  12. return memosum[n]=(n*(n+1))/2;
  13. }
  14. int n;
  15. struct Node
  16. {
  17. ll sum;
  18. int a,b,x;
  19. ll delta;
  20. bool c;
  21. }T[1 << MAXH];
  22.  
  23. void propagate(int n,int a,int b)
  24. {
  25. if(!T[n].c && !T[n].a && !T[n].b)
  26. return;
  27. if(T[n].c)
  28. {
  29. ll val=T[n].x;
  30. val *=(b-a+1);
  31. T[n].sum=val;
  32. }
  33. /*
  34. During set_range(type 'C') we cleared node.a , node.b and node.delta. So, if these are not found cleared during propagate,
  35. then some query of type 'A' or 'B' must have been called after query 'C'.
  36. Sum+=(k*delta_t + (nA+nB)*((k*(k+1))/2)
  37. where k=(b-a+1);
  38. */
  39. T[n].sum+=(b-a+1) * T[n].delta;
  40. T[n].sum+=sum(b-a+1) * (T[n].a+T[n].b);
  41.  
  42. if(a!=b)
  43. {
  44. int lt=(n<<1),rt=lt+1,m=(a+b)/2;
  45.  
  46. if(T[n].c)
  47. {
  48. T[lt].c=T[rt].c=true;
  49. T[lt].a=T[rt].a=T[lt].b=T[rt].b=0;
  50. T[lt].delta=T[rt].delta=0;
  51. T[lt].x=T[rt].x=T[n].x;
  52. }
  53.  
  54. T[lt].a+=T[n].a;
  55. T[lt].b+=T[n].b;
  56.  
  57. T[rt].a+=T[n].a;
  58. T[rt].b+=T[n].b;
  59.  
  60. ll delta=m+1-a;
  61. delta *=T[n].a;
  62. T[rt].delta+=T[n].delta+delta;
  63.  
  64. delta=b-m;
  65. delta *=T[n].b;
  66. T[lt].delta+=T[n].delta+delta;
  67. }
  68.  
  69. T[n].delta=0;
  70. T[n].a=T[n].b=T[n].x=0;
  71. T[n].c=false;
  72. }
  73.  
  74. void increment_from_left(int i,int j,int n,int a,int b)
  75. {
  76. propagate(n,a,b);
  77. if(j < a || i > b)
  78. return;
  79. if(a==b)
  80. {
  81. T[n].sum+=a-i+1;
  82. return;
  83. }
  84. int lt=(n<<1),rt=lt+1,m=(a+b)/2;
  85. if(a >=i && b <=j)
  86. {
  87. T[n].sum+=sum(b-i+1)-sum(a-i);
  88.  
  89. T[lt].delta+=a-i;
  90. ++T[lt].a;
  91.  
  92. T[rt].delta+=m+1-i;
  93. ++T[rt].a;
  94.  
  95. return;
  96. }
  97. increment_from_left(i,j,lt,a,m);
  98. increment_from_left(i,j,rt,m+1,b);
  99. T[n].sum=T[rt].sum+T[lt].sum;
  100. }
  101.  
  102. void increment_from_right(int i,int j,int n,int a,int b)
  103. {
  104. propagate(n,a,b);
  105. if(j < a || i > b)
  106. return;
  107. if(a==b)
  108. {
  109. T[n].sum+=j-b+1;
  110. return;
  111. }
  112. int lt=(n<<1),rt=lt+1,m=(a+b)/2;
  113. if(a >=i && b <=j)
  114. {
  115. T[n].sum+=sum(j-a+1)-sum(j-b);
  116.  
  117. T[lt].delta+=j-m;
  118. ++T[lt].b;
  119.  
  120. T[rt].delta+=j-b;
  121. ++T[rt].b;
  122.  
  123. return;
  124. }
  125. increment_from_right(i,j,lt,a,m);
  126. increment_from_right(i,j,rt,m+1,b);
  127. T[n].sum=T[rt].sum+T[lt].sum;
  128. }
  129. void set_range(int i,int j,int sum,int n,int a,int b)
  130. {
  131. propagate(n,a,b);
  132. if(j < a || i > b)
  133. return;
  134. if(a==b)
  135. {
  136. T[n].sum=sum;
  137. return;
  138. }
  139. int lt=(n<<1),rt=lt|1,m=(a+b)/2;
  140. if(a >=i && b <=j)
  141. {
  142. T[n].sum=(sum*(b-a+1));
  143.  
  144. T[lt].x=T[rt].x=sum;
  145. T[lt].c=T[rt].c=true;
  146.  
  147. T[lt].a=T[lt].b=0;
  148. T[rt].a=T[rt].b=0;
  149. T[lt].delta=T[rt].delta=0;
  150. return;
  151. }
  152. set_range(i,j,sum,lt,a,m);
  153. set_range(i,j,sum,rt,m+1,b);
  154. T[n].sum=T[rt].sum+T[lt].sum;
  155. }
  156.  
  157. ll query(int i,int j,int n,int a,int b)
  158. {
  159. if(j < a || i > b)
  160. return 0;
  161. propagate(n,a,b);
  162. if(a>=i && b<=j)
  163. return T[n].sum;
  164. int lt=(n<<1),rt=lt+1,m=(a+b)/2;
  165. return query(i,j,lt,a,m)+query(i,j,rt,m+1,b);
  166. }
  167.  
  168. int main()
  169. {
  170. int i,j,x,m,t,op;
  171. n=400000;
  172. scanf("%d",&m);
  173. while (m--)
  174. {
  175. scanf("%d%d%d",&op,&i,&j);
  176. switch(op)
  177. {
  178. case 1:
  179. increment_from_left(i,j,1,1,n);
  180. break;
  181. case 2:
  182. increment_from_right(i,j,1,1,n);
  183. break;
  184. case 3:
  185. scanf("%d",&x);
  186. set_range(i,j,x,1,1,n);
  187. break;
  188. case 4:
  189. printf("%lld\n",query(i,j,1,1,n));
  190. break;
  191. }
  192. }
  193. return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment