fork download
copy 
  1. #include<iostream>
  2.  
  3. #define MAX 262145
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8. LL n,m;
  9. struct tree{
  10. LL add;
  11. LL total;
  12. }T[MAX];
  13.  
  14. void update(LL Node,LL left,LL right,LL i,LL j,LL v){
  15.     if(left > j || right < i) return;
  16.     if(T[Node].add > 0){
  17.         if(left != right){
  18.             LL L = Node<<1 , R = L+1;
  19.             T[L].add += T[Node].add;
  20.             T[R].add += T[Node].add;
  21. 	    }
  22.  
  23.         T[Node].total += T[Node].add*(right-left+1);
  24.         T[Node].add = 0;
  25.     }
  26. 	if(left >= i && right <= j){
  27. 	    if(left != right){
  28.             LL L = Node<<1 , R = L+1;
  29.             T[L].add += v;
  30.             T[R].add += v;
  31. 	    }
  32.  
  33. 		T[Node].total += (right-left+1)*v;
  34. 		return;
  35. 	}
  36.  
  37. 	LL mid=(left + right)>>1, L = Node<<1 , R = L+1;
  38.    { update(L,left,mid,i,j,v);
  39.     update(R,mid+1,right,i,j,v);
  40. 	T[Node].total+=T[Node*2].total+T[Node*2+1].total;}
  41. }
  42.  
  43. LL query(LL Node,LL left,LL right,LL i,LL j){
  44.     if(left > j || right < i) return 0;
  45.  
  46.     if(T[Node].add > 0){
  47.         if(left != right){
  48.             LL L = Node<<1 , R = L+1;
  49.             T[L].add += T[Node].add;
  50.             T[R].add += T[Node].add;
  51. 	    }
  52.  
  53.         T[Node].total += T[Node].add*(right-left+1);
  54.         T[Node].add = 0;
  55.     }
  56.  
  57.     if(left >= i && right <= j)return T[Node].total;
  58.  
  59.     LL mid = (right+left)/2, L = Node<<1 , R = L+1;
  60.     LL ret =0;
  61.     ret+= query(L,left,mid,i,j);
  62.     ret+= query(R,mid+1,right,i,j);
  63.     return ret;
  64. }
  65.  
  66. int main(){
  67. LL t;
  68. cin >> t;
  69. while(t--){
  70. cin >> n >> m;
  71. 	for(LL i=0;i<MAX;i++)
  72. 		T[i].total = T[i].add = 0;
  73. while(m--){
  74. 	LL q,a,b,k;
  75. 	cin >> q >> a >> b;
  76. 		switch(q){
  77. 			case 0:cin >> k;
  78. 				update(1,1,MAX/2,a,b,k);break;
  79. 			case 1:cout << query(1,1,MAX/2,a,b) << endl;break;
  80. 		}
  81. }
  82. }
  83. return 0;
  84. }
Success #stdin #stdout 0s 7200KB
comments (?)
stdin
copy 
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
copy 
80
1328
https://ideone.com/Geubnq
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!