fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> 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 pref[N];
  16. int f[18][N]; // f[k][i] = max của đoạn bắt đầu từ i và có độ dài là 2^k
  17.  
  18. int nxt[18][N]; 
  19. ll cost[18][N]; 
  20.  
  21. void precompute() {
  22. 	for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i]; 
  23.  
  24. 	for (int i = 1; i <= n; i++) f[0][i] = a[i];  
  25.  
  26. 	for (int k = 1; (1 << k) <= n; k++) {
  27. 		for (int i = 1; i + (1 << k) - 1 <= n; i++) {
  28. 			f[k][i] = max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]); 
  29. 		}
  30. 	}
  31. }
  32.  
  33. ll getSum(int l, int r) {
  34. 	return pref[r] - pref[l - 1]; 
  35. }
  36.  
  37. int getMax(int l, int r) {
  38. 	int k = log2(r - l + 1); 
  39. 	return max(f[k][l], f[k][r - (1 << k) + 1]); 
  40. }
  41.  
  42. // Tìm vị trí j gần nhất bên phải sao cho a[j] > a[i]
  43. int findNext(int i) {
  44. 	int l = i + 1, r = n, ans = n + 1;  
  45. 	while (l <= r) {
  46. 		int mid = (l + r) >> 1; 
  47.  
  48. 		if (getMax(i, mid) > a[i]) {
  49. 			ans = mid; 
  50. 			r = mid - 1; 
  51. 		}
  52. 		else {
  53. 			l = mid + 1; 
  54. 		}
  55. 	}
  56.  
  57. 	return ans; 
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(0); cin.tie(0);  	
  62. 	cin >> n >> q; 
  63. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  64.  
  65. 	precompute();   
  66.  
  67. 	// nxt[0][i] = vị trí j gần nhất bên phải sao cho a[j] > a[i]
  68. 	// Khi đó a[i] chính là max của đoạn [i, nxt[0][i] - 1]
  69. 	// cost[0][i] = Tổng số thao tác ít nhất cần sử dụng của đoạn [i, nxt[0][i] - 1]
  70. 	for (int i = 1; i <= n; i++) {
  71. 		nxt[0][i] = findNext(i); 
  72. 		cost[0][i] = 1ll * (nxt[0][i] - i) * a[i] - getSum(i, nxt[0][i] - 1);
  73. 	}
  74. 	nxt[0][n + 1] = n + 1; 
  75. 	cost[0][n + 1] = 0;  
  76.  
  77. 	for (int k = 1; k <= 17; k++) {
  78. 		for (int i = 1; i <= n + 1; i++) {
  79. 			nxt[k][i] = nxt[k - 1][nxt[k - 1][i]]; 
  80. 			cost[k][i] = cost[k - 1][i] + cost[k - 1][nxt[k - 1][i]]; 
  81. 		}
  82. 	}
  83.  
  84. 	while (q--) {
  85. 		int l, r; 
  86. 		cin >> l >> r; 
  87.  
  88. 		ll ans = 0;  
  89. 		for (int k = 17; k >= 0; k--) {
  90. 			if (nxt[k][l] <= r) {
  91. 				ans += cost[k][l]; 
  92. 				l = nxt[k][l]; 
  93. 			}
  94. 		}
  95. 		ans += 1ll * (r - l + 1) * a[l] - getSum(l, r); // đoạn còn dư ra 
  96.  
  97. 		cout << ans << '\n'; 
  98. 	}
  99. }
Success #stdin #stdout 0.01s 48792KB
comments (?)
stdin
copy 
5 3
2 10 4 2 5
3 5
2 2
1 4
stdout
copy 
2
0
14
https://ideone.com/IsGYaa
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!