fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. #define ll long long
  5.  
  6. struct node{
  7. 	ll sum,upsum;
  8. 	int lft,ryt;
  9. 	bool isup;
  10. 	void init(int l,int r){
  11. 		lft = l;
  12. 		ryt = r;
  13. 		isup = false;
  14. 		upsum = 0;
  15. 	}
  16. 	void merge(ll a,ll b){
  17. 		sum = a+b;
  18. 	}
  19.  
  20. }segtree[4*100005];
  21.  
  22. int n,arr[100005];
  23.  
  24. void split(int t,int l,int r){
  25. 	if(l!=r){
  26. 		segtree[2*t].upsum += segtree[t].upsum;
  27. 		segtree[2*t].isup = true;
  28. 		segtree[2*t+1].upsum += segtree[t].upsum;
  29. 		segtree[2*t+1].isup = true;
  30. 	}
  31. 	segtree[t].sum += (r-l+1)*segtree[t].upsum;
  32. 	segtree[t].upsum = 0;
  33. 	segtree[t].isup = false;
  34. }
  35.  
  36. ll build(int t,int i,int j){
  37. 	if(i==j){
  38. 		segtree[t].init(i,j);
  39. 		segtree[t].sum = 0;
  40. 		return segtree[t].sum;
  41. 	}
  42. 	int l=2*t,mid=(i+j)/2;
  43. 	ll a,b;
  44. 	a = build(l,i,mid);
  45. 	b = build(l+1,mid+1,j);
  46. 	segtree[t].init(i,j);
  47. 	segtree[t].merge(a,b);
  48. 	return segtree[t].sum;
  49. }
  50.  
  51. ll query(int t,int i,int j,int ri,int rj){
  52. 	if(segtree[t].isup)
  53. 		split(t,segtree[t].lft,segtree[t].ryt);
  54. 	if(ri <=i && rj>=j){
  55. 		return segtree[t].sum;
  56. 	}
  57. 	int l=2*t,mid=(i+j)/2;
  58. 	if(rj<=mid)
  59. 		return query(l,i,mid,ri,rj);
  60. 	if(ri>mid)
  61. 		return query(l+1,mid+1,j,ri,rj);
  62. 	ll a,b;
  63. 	a = query(l,i,mid,ri,mid);
  64. 	b = query(l+1,mid+1,j,mid+1,rj);
  65. 	return a+b;
  66. }
  67.  
  68. ll update(int t,int i,int j,int ri,int rj,int v){
  69. 	if(segtree[t].isup)
  70. 		split(t,segtree[t].lft,segtree[t].ryt);
  71. 	if(ri <=i && rj>=j){
  72. 		segtree[t].upsum +=v;
  73. 		segtree[t].isup = true;
  74. 		split(t,segtree[t].lft,segtree[t].ryt);
  75. 		return segtree[t].sum;
  76. 	}
  77. 	int l=2*t,mid=(i+j)/2;
  78. 	if(j<ri || i>rj)
  79.      	return 0;
  80. 	ll a,b;
  81. 	a = update(l,i,mid,ri,rj,v);
  82. 	b = update(l+1,mid+1,j,mid+1,rj,v);
  83. 	segtree[t].merge(a,b);
  84. 	return segtree[t].sum;
  85. }
  86.  
  87.  
  88. int main(){
  89. 	int t,q,p,r,c,v;
  90. 	cin>>t;
  91. 	while(t--){
  92. 		cin>>n>>q;
  93. 		build(1,1,n);
  94. 		while(q--){
  95. 			cin>>c>>p>>r;
  96. 			if(c==0){
  97. 				cin>>v;
  98. 				update(1,1,n,p,r,v);
  99. 			}
  100. 			else{
  101. 				cout<<query(1,1,n,p,r)<<'\n';
  102. 			}
  103. 		}
  104. 	}
  105. 	return 0;
  106. }
Success #stdin #stdout 0s 14680KB
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
348
https://ideone.com/Yb0ZVO
http://w...content-available-to-author-only...j.com/problems/HORRIBLE/
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!