fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. ll int node[1000000];
  6. ll int lazy[1000000];
  7.  
  8. int update(int x,int y,int l,int r,long long int v,int i){ // v should be long long int
  9. if (lazy[i]!=0){
  10. node[i]+=((r-l+1)*lazy[i]);
  11. if (l!=r){
  12. lazy[2*i+1]+=lazy[i];
  13. lazy[2*i+2]+=lazy[i];
  14. }
  15. lazy[i]=0;
  16. }
  17. if (y<l||x>r||l>r) return 0;
  18. if (x<=l&&y>=r){
  19. node[i]+= ((r-l+1)*v); // here you get overflow due to int v
  20. if (l!=r){
  21. lazy[2*i+1]+=v;
  22. lazy[2*i+2]+=v;
  23. }
  24. return 0;
  25. }
  26. int mid = (l+r)/2;
  27. update(x,y,l,mid,v,2*i+1);
  28. update(x,y,mid+1,r,v,2*i+2);
  29. node[i] = node[2*i+1]+node[2*i+2];
  30. return 0;
  31. }
  32.  
  33. ll int querytree(int x,int y,int l,int r,int i){
  34. if (lazy[i]!=0){
  35. node[i]+=((r-l+1)*lazy[i]);
  36. if (l!=r){
  37. lazy[2*i+1]+=lazy[i];
  38. lazy[2*i+2]+=lazy[i];
  39. }
  40. lazy[i]=0;
  41. }
  42.  
  43. if (l>r||y<l||x>r) return 0; // apply this condition after solving lazy because there are some node which needs to be solve
  44.  
  45. if (l>=x&&r<=y) return node[i];
  46. else{ // no need of this else because if function return value then rest of code are unreachable but its OK
  47. int mid = (l+r)/2;
  48. return (querytree(x,y,l,mid,2*i+1)+querytree(x,y,mid+1,r,2*i+2));
  49. }
  50. }
  51.  
  52. int main(){
  53. int t;
  54. scanf("%d",&t);
  55. while (t--){
  56. int n,query;
  57. scanf("%d%d",&n,&query);
  58. while (query--){
  59. int ch,p,q;
  60. scanf("%d%d%d",&ch,&p,&q);
  61. p--;
  62. q--;
  63. if (ch==0){
  64. long long int v;
  65. scanf("%lld",&v);
  66. update(p,q,0,n-1,v,0);
  67. }
  68. else{
  69. printf("%lld\n",querytree(p,q,0,n-1,0));
  70. }
  71. }
  72. memset(node,0,sizeof(node));
  73. memset(lazy,0,sizeof(lazy));
  74. }
  75. return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 19040KB
stdin
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
80
508