fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12. const int LOG = 18;  
  13.  
  14. int n, q; 
  15. int a[N]; 
  16.  
  17. ll pref[N];
  18. int f[LOG][N]; // f[k][i] = Max của đoạn bắt đầu từ i và có độ dài là 2^k 
  19.  
  20. int log2_floor(int x) {
  21. 	return 31 - __builtin_clz(x);
  22. }
  23.  
  24. void precompute() {
  25. 	for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i]; 
  26.  
  27. 	for (int i = 1; i <= n; i++) f[0][i] = a[i];  
  28.  
  29. 	for (int k = 1; k < LOG; k++) {
  30. 		for (int i = 1; i + (1 << k) - 1 <= n; i++) {
  31. 			f[k][i] = max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]); 
  32. 		}
  33. 	}
  34. }
  35.  
  36. ll getSum(int l, int r) {
  37. 	return pref[r] - pref[l - 1]; 
  38. }
  39.  
  40. int getMax(int l, int r) {
  41. 	int k = log2_floor(r - l + 1); 
  42. 	return max(f[k][l], f[k][r - (1 << k) + 1]); 
  43. }
  44.  
  45. // Vị trí j nhỏ nhất > i sao cho a[j] > a[i]
  46. int nextGreater(int i) {
  47. 	int l = i + 1, r = n, ans = n + 1;  
  48. 	while (l <= r) {
  49. 		int mid = (l + r) >> 1; 
  50. 		if (getMax(i, mid) > a[i]) {
  51. 			ans = mid; 
  52. 			r = mid - 1; 
  53. 		}
  54. 		else {
  55. 			l = mid + 1; 
  56. 		}
  57. 	}
  58. 	return ans; 
  59. }
  60.  
  61. int nxt[LOG][N]; 
  62. ll cost[LOG][N];
  63.  
  64. int main() {
  65. 	ios::sync_with_stdio(false); 
  66. 	cin.tie(nullptr);  	
  67. 	cin >> n >> q; 
  68. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  69.  
  70. 	precompute();   
  71.  
  72. 	// Đặt nxt[0][i] = nextGreater(i)
  73. 	// Khi đó a[i] chính là max của đoạn [i, nxt[0][i] - 1]
  74. 	// cost[0][i] = Số thao tác ít nhất cần sử dụng khi xét đoạn [i, nxt[0][i] - 1]
  75. 	for (int i = 1; i <= n; i++) {
  76. 		nxt[0][i] = nextGreater(i); 
  77. 		cost[0][i] = 1ll * (nxt[0][i] - i) * a[i] - getSum(i, nxt[0][i] - 1);
  78. 	}
  79. 	nxt[0][n + 1] = n + 1; 
  80. 	cost[0][n + 1] = 0;  
  81.  
  82. 	for (int k = 1; k < LOG; k++) {
  83. 		for (int i = 1; i <= n + 1; i++) {
  84. 			nxt[k][i] = nxt[k - 1][nxt[k - 1][i]]; 
  85. 			cost[k][i] = cost[k - 1][i] + cost[k - 1][nxt[k - 1][i]]; 
  86. 		}
  87. 	}
  88.  
  89. 	while (q--) {
  90. 		int l, r; 
  91. 		cin >> l >> r; 
  92.  
  93. 		ll ans = 0;  
  94. 		for (int k = LOG - 1; k >= 0; k--) {
  95. 			if (nxt[k][l] <= r) {
  96. 				ans += cost[k][l]; 
  97. 				l = nxt[k][l]; 
  98. 			}
  99. 		}
  100. 		ans += 1ll * (r - l + 1) * a[l] - getSum(l, r); // đoạn còn dư ra 
  101.  
  102. 		cout << ans << '\n'; 
  103. 	}
  104. }
Success #stdin #stdout 0.01s 48652KB
comments (?)
stdin 
5 3
2 10 4 2 5
3 5
2 2
1 4
stdout 
2
0
14
https://ideone.com/zbo6As
language:
C++14 (gcc 8.3)
created:
8 days 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!