fork download
copy 
  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 = 5e5 + 5; 
  12.  
  13. // Bài này ta sẽ sử dụng Stack cùng với MergeSort Tree (vector)
  14. int n; 
  15. int a[N]; 
  16. int l_less[N]; // l_less[i] = Phần tử gần nhất bên trái < a[i]
  17. int r_less[N]; // r_less[i] = Phần tử gần nhất bên phải < a[i]
  18. int l_greater[N]; // l_greater[i] = Phần tử gần nhất bên trái > a[i]
  19. int r_greater[N];  // r_greater[i] = Phần tử gần nhất bên phải > a[i]
  20.  
  21. void precompute() {
  22. 	vector<int> st;  
  23. 	for (int i = 1; i <= n; i++) {
  24. 		while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();  
  25. 		l_less[i] = st.empty() ? 0 : st.back();   
  26. 		st.push_back(i);  
  27. 	}
  28.  
  29. 	st.clear();   
  30. 	for (int i = n; i >= 1; i--) {
  31. 		while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();  
  32. 		r_less[i] = st.empty() ? n + 1 : st.back();   
  33. 		st.push_back(i);  
  34. 	}
  35.  
  36. 	st.clear(); 
  37. 	for (int i = 1; i <= n; i++) {
  38. 		while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();  
  39. 		l_greater[i] = st.empty() ? 0 : st.back();   
  40. 		st.push_back(i);  
  41. 	}
  42.  
  43. 	st.clear();   
  44. 	for (int i = n; i >= 1; i--) {
  45. 		while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();  
  46. 		r_greater[i] = st.empty() ? n + 1 : st.back();   
  47. 		st.push_back(i);  
  48. 	}
  49. }
  50.  
  51. vector<int> seg[4 * N]; // seg[id] = vector chứa các phần tử thuộc đoạn [l, r] do nút id quản lí, theo thứ tự tăng dần
  52.  
  53. void initTree() {
  54. 	for (int id = 1; id <= 4 * n; id++) seg[id].clear();  
  55. }
  56.  
  57. // O(nlogn)
  58. void build(int type, int id, int l, int r) {
  59. 	if (l == r) {
  60. 		seg[id].push_back(type ? r_greater[l] : l_greater[l]); 
  61. 		return;
  62. 	}
  63. 	int mid = (l + r) >> 1;   
  64. 	build(type, id * 2, l, mid);  
  65. 	build(type, id * 2 + 1, mid + 1, r);  
  66. 	merge(seg[id * 2].begin(), seg[id * 2].end(), seg[id * 2 + 1].begin(), seg[id * 2 + 1].end(), back_inserter(seg[id])); 
  67. }
  68.  
  69. // Đếm xem có bao nhiêu chỉ số i thuộc đoạn [u, v] sao cho l_greater[i] < x
  70. // O(log^2(n))
  71. int countLess(int id, int l, int r, int u, int v, int x) {
  72. 	if (l > v || r < u) return 0;  
  73. 	if (u <= l && r <= v) {
  74. 		int pos = lower_bound(seg[id].begin(), seg[id].end(), x) - seg[id].begin();    
  75. 		return pos;
  76. 	}
  77. 	int mid = (l + r) >> 1;  
  78. 	return countLess(id * 2, l, mid, u, v, x) + countLess(id * 2 + 1, mid + 1, r, u, v, x); 
  79. }
  80.  
  81. // Đếm xem có bao nhiêu chỉ số i thuộc đoạn [u, v] sao cho r_greater[i] > x
  82. // O(log^2(n))
  83. int countGreater(int id, int l, int r, int u, int v, int x) {
  84. 	if (l > v || r < u) return 0;  
  85. 	if (u <= l && r <= v) {
  86. 		int pos = upper_bound(seg[id].begin(), seg[id].end(), x) - seg[id].begin();    
  87. 		return seg[id].size() - pos;  
  88. 	}
  89. 	int mid = (l + r) >> 1;  
  90. 	return countGreater(id * 2, l, mid, u, v, x) + countGreater(id * 2 + 1, mid + 1, r, u, v, x); 
  91. }
  92.  
  93. int main() {
  94. 	ios::sync_with_stdio(false); 
  95. 	cin.tie(nullptr); 	
  96. 	cin >> n; 
  97. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  98.  
  99. 	precompute();   
  100.  
  101. 	// Ta sẽ đi đếm số đoạn [l, r] trong từng trường hợp sau:
  102. 	// Trường hợp 1: a[l] đóng vai trò là min
  103. 	// - Nhận xét: a[l] sẽ là min của đoạn [l, r] với r thuộc đoạn [l, r_less[l] - 1]
  104. 	// => Với mỗi l, đếm có bao nhiêu r thuộc đoạn [l, r_less[l] - 1] sao cho a[r] là max của đoạn [l, r]
  105. 	// => Với mỗi l, đếm có bao nhiêu r thuộc đoạn [l, r_less[l] - 1] sao cho l_greater[r] < l
  106. 	// Fact: ta cũng đã đếm luôn những case l = r
  107. 	initTree();  
  108. 	build(0, 1, 1, n);  
  109. 	ll ans = 0;  
  110. 	for (int l = 1; l <= n; l++) {
  111. 		ans += countLess(1, 1, n, l, r_less[l] - 1, l); 
  112. 	} // O(nlog^2(n))
  113.  
  114. 	// Trường hợp 2: a[r] đóng vai trò là min
  115. 	// - Nhận xét: a[r] sẽ là min của đoạn [l, r] với l thuộc đoạn [l_less[r] + 1, r]
  116. 	// => Với mỗi r, đếm có bao nhiêu l thuộc đoạn [l_less[r] + 1, r] sao cho a[l] là max của đoạn [l, r]
  117. 	// => Với mỗi r, đếm có bao nhiêu l thuộc đoạn [l_less[r] + 1, r] sao cho r_greater[l] > r
  118. 	// Chú ý: Để tránh đếm trùng lại case l = r thì ta đếm trong đoạn [l_less[r] + 1, r - 1]
  119. 	initTree();  
  120. 	build(1, 1, 1, n);  
  121. 	for (int r = 1; r <= n; r++) {
  122. 		ans += countGreater(1, 1, n, l_less[r] + 1, r - 1, r);  
  123. 	} // O(nlog^2(n))
  124.  
  125. 	cout << ans << '\n'; 
  126. }
Success #stdin #stdout 0.02s 59400KB
comments (?)
stdin
copy 
8
2 5 1 4 3 8 7 6
stdout
copy 
17
https://ideone.com/Y47UAm
language:
C++14 (gcc 8.3)
created:
223 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!