fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll int arr[100005];
  5. ll int tree[400005] = {0};
  6. ll int lazy[400005] = {0};
  7.  
  8. ll int sum(ll int a,ll int b)
  9. {
  10. 	return (a + b);
  11. }
  12.  
  13. void build_tree(int node,int a,int b)
  14. {
  15. 	if(a > b)
  16. 		return ;
  17. 	if(a == b)
  18. 	{
  19. 		tree[node] = arr[a];
  20. 		return ;
  21. 	}
  22.  
  23. 	build_tree(2*node,a,(a+b)/2);
  24. 	build_tree(2*node + 1,1 + (a+b)/2,b);
  25. 	tree[node] = sum(tree[2*node],tree[(2*node) + 1]);
  26. }
  27.  
  28. void update_tree(int node,int a,int b,int i,int j,int val)
  29. {
  30. 	if(lazy[node] != 0)
  31. 	{
  32. 		tree[node] += (b - a + 1) * lazy[node];
  33. 		if(a != b)
  34. 		{
  35. 			lazy[2*node] += lazy[node];
  36. 			lazy[(2*node) + 1] += lazy[node];
  37. 		}
  38. 		lazy[node] = 0;
  39. 	}
  40. 	// because of past
  41.  
  42. 	if(a > b      ||   a > j   || b < i)
  43. 		return;
  44. 	if(a >= i && b <= j)
  45. 	{
  46. 		tree[node] += (b - a + 1) * val;
  47. 		if(a != b)
  48. 		{
  49. 			lazy[node*2] += val;
  50. 			lazy[(2*node) + 1] += val;
  51. 		}
  52. 		return ;
  53. 	}
  54.  
  55. 	update_tree(2*node,a,(a+b)/2,i,j,val);
  56. 	update_tree((2*node) + 1,1 + ((a+b)/2),b,i,j,val);
  57. 	tree[node] = sum(tree[2*node],tree[(2*node) + 1]);
  58.  
  59. }
  60.  
  61. ll int query_tree(int node,int a,int b,int i,int j)
  62. {
  63. 		if(lazy[node] != 0)
  64. 		{
  65. 			tree[node] += (b - a + 1) * lazy[node];
  66. 			if(a != b)
  67. 			{
  68. 				lazy[2*node] += lazy[node];
  69. 				lazy[(2*node) + 1] += lazy[node];
  70. 			}
  71. 			lazy[node] = 0;
  72. 		}
  73.  
  74. 		if(a > b      ||   a > j   || b < i)
  75. 			return 0;
  76.  
  77.  
  78. 	// because of past
  79.  
  80. 	if(a >= i && b <= j)
  81. 	{
  82. 		return tree[node];
  83. 	}
  84.  
  85. 	ll int q1 = query_tree(2*node,a,(a + b)/2,i,j);
  86. 	ll int q2 = query_tree((2*node) + 1,1 + ((a + b)/2),b,i,j);
  87. 	return sum(q1,q2);
  88. }
  89.  
  90. int main()
  91. {
  92. 	ios_base::sync_with_stdio(0);
  93. 	int N,type,l,r,val,Q,T;
  94. 	cin >> T;
  95.  
  96. 	while(T--)
  97. 	{
  98. 		cin >> N >> Q;
  99. 		for(int i = 0;i <= 4*N;i++)
  100. 		{
  101. 			tree[i] = lazy[i] = 0;
  102. 		}
  103. 	//	build_tree(1,0,N - 1);
  104.  
  105. 		while(Q--)
  106. 		{
  107. 			cin >> type;
  108. 			if(type == 0)			//  update
  109. 			{
  110. 				cin >> l >> r >> val;
  111. 				update_tree(1,0,N - 1,l - 1,r - 1,val);
  112. 			}
  113. 			else
  114. 			{
  115. 				cin >> l >> r;
  116. 				cout << query_tree(1,0,N - 1,l - 1,r - 1) << endl;
  117. 			}
  118. 		}
  119.  
  120. 	}
  121. 	return 0;
  122.  
  123. }
Success #stdin #stdout 0s 10496KB
comments (?)
stdin
copy 
Input:
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 
Standard output is empty
https://ideone.com/emfOqD
language:
C++14 (gcc 8.3)
created:
7 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!