fork download
copy 
  1. // first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front priority_queue
  2.  
  3. #ifndef ONLINE_JUDGE
  4. #include "debug.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define debug(...) 42
  9. #endif
  10.  
  11. #define ll long long
  12. #define all(a)      (a).begin(),(a).end()
  13. using pll = pair < ll, ll >;
  14.  
  15. const ll sz = 8e5 + 10;
  16. vector<vector<ll>> tree(sz);
  17. vector<vector<ll>> pre(sz);
  18. vector<ll> sum(sz);
  19. ll curVal;
  20.  
  21. void merge(ll node, ll x, ll y) {
  22. 	ll i = 0, j = 0;
  23. 	tree[node].clear();
  24. 	pre[node].clear();
  25. 	sum[node] = 0;
  26.  
  27. 	while (i < tree[x].size()) {
  28. 		tree[node].push_back(tree[x][i]);
  29. 		i++;
  30. 	}
  31.  
  32. 	i = 0;
  33. 	if (tree[node].size())	i = tree[node].back();
  34.  
  35. 	while (j < tree[y].size()) {
  36. 		ll t = max(i, tree[y][j]);
  37. 		sum[node] += t - tree[y][j];
  38. 		tree[node].push_back(t);
  39. 		j++;
  40. 	}
  41.  
  42. 	i = j = 0;
  43. 	while (i < tree[node].size()) {
  44. 		j += tree[node][i];	i++;
  45. 		pre[node].push_back(j);
  46. 	}
  47. }
  48.  
  49. void update(ll node, ll l, ll r, ll idx, ll val) {
  50. 	if (l > r)	return;
  51. 	if (l == r) {
  52. 		tree[node] = {val};
  53. 		pre[node] = {val};
  54. 		return;
  55. 	}
  56.  
  57. 	ll mid = (l + r) / 2;
  58. 	if (idx <= mid)	update(2 * node, l, mid, idx, val);
  59. 	else	update(2 * node + 1, mid + 1, r, idx, val);
  60.  
  61. 	merge(node, node * 2, node * 2 + 1);
  62. }
  63.  
  64. ll get(ll node, ll l, ll r, ll rangeL, ll rangeR, ll &val) {
  65. 	if (l > r or l > rangeR or r < rangeL)	return 0;
  66.  
  67. 	if (rangeL <= l and r <= rangeR)	{
  68. 		ll x = sum[node];
  69. 		if (tree[node].size() != 0) {
  70. 			ll i = lower_bound(all(tree[node]), val) - tree[node].begin();
  71. 			if (i > 0)	x += (i * val) - pre[node][i - 1];
  72. 			val = max(val, tree[node].back());
  73. 		}
  74. 		return x;
  75. 	}
  76.  
  77. 	ll mid = (l + r) / 2;
  78. 	ll idx = get(node * 2, l, mid, rangeL, rangeR, val);
  79. 	idx += get(node * 2 + 1, mid + 1, r, rangeL, rangeR, val);
  80. 	return idx;
  81. }
  82.  
  83.  
  84. int32_t main() {
  85. 	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);
  86.  
  87. 	ll t, i, j, y, x, n, z, k;
  88. 	cin >> n >> t;
  89. 	vector<ll> val, ans;
  90.  
  91. 	for (ll i = 1; i <= n; i++) {
  92. 		cin >> x;	val.push_back(x);
  93. 		update(1, 1, n, i, x);
  94. 	}
  95.  
  96. 	while (t--) {
  97. 		cin >> x >> y;
  98. 		ll mn = 0;
  99. 		z = get(1, 1, n, x, y, mn);
  100. 		ans.push_back(z);
  101. 	}
  102.  
  103. 	debug(ans);
  104. 	for (auto &zx : ans)	cout << zx << " ";
  105. }
  106.  
  107.  
Success #stdin #stdout 0.02s 46828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/BQ4TEW
language:
C++14 (clang 8.0)
created:
3 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!