fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<ll, ll> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11.  
  12. int n, q;  
  13. int a[N]; 
  14.  
  15. ll seg[4 * N];  // seg[id]  = tổng đoạn [l, r]
  16. ii lazy[4 * N]; // lazy[id] = {cnt, C}: đoạn [l, r] cần cộng (tổng từ l tới r) cnt lần
  17. 				//                    : mỗi phần tử trong đoạn [l, r] cần trừ đi cho C
  18.  
  19. void build(int id, int l, int r) {
  20. 	if (l == r) {
  21. 		seg[id] = a[l]; 
  22. 		return; 
  23. 	}
  24.  
  25. 	int mid = (l + r) >> 1; 
  26. 	build(id << 1, l, mid); 
  27. 	build(id << 1 | 1, mid + 1, r); 
  28.  
  29. 	seg[id] = seg[id << 1] + seg[id << 1 | 1]; 
  30. }
  31.  
  32. void push(int id, int l, int r) {
  33. 	if (lazy[id].first > 0) {
  34. 		int mid = (l + r) >> 1;  
  35.  
  36. 		seg[id << 1] += 1ll * (mid + l) * (mid - l + 1) / 2 * lazy[id].first;  
  37. 		seg[id << 1] -= 1ll * (mid - l + 1) * lazy[id].second;  
  38. 		lazy[id << 1].first += lazy[id].first;  
  39. 		lazy[id << 1].second += lazy[id].second;   
  40.  
  41. 		seg[id << 1 | 1] += 1ll * (r + mid + 1) * (r - mid) / 2 * lazy[id].first;   
  42. 		seg[id << 1 | 1] -= 1ll * (r - mid) * lazy[id].second;   
  43. 		lazy[id << 1 | 1].first += lazy[id].first;  
  44. 		lazy[id << 1 | 1].second += lazy[id].second; 
  45.  
  46. 		lazy[id] = {0, 0}; 
  47. 	}
  48. }
  49.  
  50. void update(int id, int l, int r, int u, int v, ll C) {
  51. 	if (l > v || r < u) return;  
  52.  
  53. 	if (u <= l && r <= v) {
  54. 		seg[id] += 1ll * (r + l) * (r - l + 1) / 2; 
  55. 		seg[id] -= 1ll * (r - l + 1) * C;  
  56. 		lazy[id].first++, lazy[id].second += C; 
  57. 		return; 
  58. 	}
  59.  
  60. 	push(id, l, r);  
  61.  
  62. 	int mid = (l + r) >> 1; 
  63. 	update(id << 1, l, mid, u, v, C); 
  64. 	update(id << 1 | 1, mid + 1, r, u, v, C); 
  65.  
  66. 	seg[id] = seg[id << 1] + seg[id << 1 | 1]; 
  67. }
  68.  
  69. ll get(int id, int l, int r, int u, int v) {
  70. 	if (l > v || r < u) return 0; 
  71.  
  72. 	if (u <= l && r <= v) return seg[id]; 
  73.  
  74. 	push(id, l, r); 
  75.  
  76. 	int mid = (l + r) >> 1; 
  77. 	return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v); 
  78. }
  79.  
  80. int main() {
  81. 	ios::sync_with_stdio(0); cin.tie(0);  	
  82. 	cin >> n >> q; 
  83. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  84.  
  85. 	build(1, 1, n);  
  86.  
  87. 	while (q--) {
  88. 		int type, l, r; 
  89. 		cin >> type >> l >> r; 
  90.  
  91. 		if (type == 1) {
  92. 			update(1, 1, n, l, r, l - 1);  
  93. 		}
  94. 		else {
  95. 			cout << get(1, 1, n, l, r) << '\n'; 
  96. 		}
  97. 	}
  98. }
Success #stdin #stdout 0.01s 5724KB
comments (?)
stdin
copy 
5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5
stdout
copy 
17
32
https://ideone.com/ebnUyL
language:
C++14 (gcc 8.3)
created:
1 year 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!