fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define MAXN 1000000
  4.  
  5. using namespace std;
  6.  
  7. int N;
  8. long long a[MAXN];
  9.  
  10. struct SegTree
  11. {
  12. 	long long tree[2 * MAXN];
  13. 	long long lazy[2 * MAXN];
  14.  
  15. 	void build(int l, int r, int idx)
  16. 	{
  17. 		if(l == r)
  18. 		{
  19. 			tree[idx] = a[l];
  20. 			return;	
  21. 		}
  22.  
  23. 		int mid = l + (r - l) / 2;
  24. 		build(l, mid, 2 * idx + 1);
  25. 		build(mid + 1, r, 2 * idx + 2);
  26.  
  27. 		tree[idx] = tree[2 * idx + 1] + tree[2 * idx + 2];
  28. 	}
  29.  
  30. 	long long Query(int qL, int qR, int l, int r, int idx)
  31. 	{	
  32. 		if(lazy[idx])
  33. 		{
  34. 			tree[idx] += (r - l + 1) * lazy[idx];
  35.  
  36. 			if(l != r)
  37. 			{
  38. 				lazy[2 * idx + 1] += lazy[idx];
  39. 				lazy[2 * idx + 2] += lazy[idx];
  40. 			}
  41.  
  42. 			lazy[idx] = 0;
  43. 		}
  44.  
  45. 		//printf("{%d, %d}:    %lld\n", l, r, tree[idx]);
  46.  
  47. 		if(l > qR || r < qL)
  48. 			return 0;
  49.  
  50. 		if(qL <= l && r <= qR)
  51. 			return tree[idx];
  52.  
  53. 		int mid = l + (r - l) / 2;
  54. 		return Query(qL, qR, l, mid, 2 * idx + 1) + Query(qL, qR, mid + 1, r, 2 * idx + 2);
  55. 	}
  56.  
  57. 	int update(int qL, int qR, int l, int r, int idx, long long inc)
  58. 	{
  59. 		if(lazy[idx])
  60. 		{
  61. 			tree[idx] += (r - l + 1) * lazy[idx];
  62.  
  63. 			if(l != r)
  64. 			{
  65. 				lazy[2 * idx + 1] += lazy[idx];
  66. 				lazy[2 * idx + 2] += lazy[idx];				    
  67. 			}
  68.  
  69. 			lazy[idx] = 0;
  70. 		}
  71.  
  72.  
  73. 		if(l > qR || r < qL)
  74. 			return 0;
  75.  
  76. 		if(qL <= l && r <= qR)
  77. 		{
  78. 			lazy[idx] = inc;
  79.  
  80. 			if(lazy[idx])
  81. 			{
  82. 				tree[idx] += (r - l + 1) * lazy[idx];
  83.  
  84. 				if(l != r)
  85. 				{
  86. 					lazy[2 * idx + 1] += lazy[idx];
  87. 					lazy[2 * idx + 2] += lazy[idx];							    
  88. 				}
  89.  
  90. 				lazy[idx] = 0;
  91. 			}
  92.  
  93.  
  94. 			return 1;
  95. 		}
  96.  
  97. 		int mid = l + (r - l) / 2;
  98. 		update(qL, qR, l, mid, 2 * idx + 1, inc);
  99. 		update(qL, qR, mid + 1, r, 2 * idx + 2, inc);
  100.  
  101. 		tree[idx] = tree[2 * idx + 1] + tree[2 * idx + 2];
  102.  
  103. 		return 1;
  104. 	}
  105.  
  106. };
  107.  
  108. void read()
  109. {
  110. 	scanf("%d", &N);
  111.  
  112. 	for(int i = 0; i < N; i++)
  113. 		a[i] = 0;
  114. }
  115.  
  116. SegTree t;
  117.  
  118. void solve()
  119. {
  120. 	memset(t.lazy, 0, sizeof(t.lazy));
  121. 	memset(t.tree, 0, sizeof(t.tree));
  122.  
  123. 	t.build(0, N - 1, 0);
  124.  
  125. 	int M;
  126. 	scanf("%d", &M);
  127.  
  128. 	for(int i = 0; i < M; i++)
  129. 	{
  130. 		int type, l, r;
  131. 		scanf("%d %d %d", &type, &l, &r);
  132.  
  133. 		l--, r--;
  134.  
  135. 		if(type == 1)
  136. 			printf("%lld\n", t.Query(l, r, 0, N - 1, 0));
  137. 		else
  138. 		{
  139. 			long long v;
  140. 			scanf("%lld", &v);
  141. 			t.update(l, r, 0, N - 1, 0, v);
  142. 		}
  143. 	}
  144. }
  145.  
  146. int main()
  147. {
  148. 	int T;
  149. 	scanf("%d", &T);
  150.  
  151. 	for(int i = 0; i < T; i++)
  152. 	{
  153. 		read();
  154. 		solve();
  155. 	}
  156.  
  157. 	return 0;
  158. }
  159.  
  160.  
Success #stdin #stdout 0s 42544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kUe4z9
problem HORRIBLE, based on SPOJ submission 14577638 (C++14), 2015-07-01 10:35:22
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!