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. // - Đây là một bài tương đối đơn giản, ta chỉ cần nghĩ ra thuật O(n^2), sau đó tối ưu lên bằng CTDL (Fenwick Tree, Segment Tree,...)
  12. // - Gọi beg, last lần lượt là vị trí của phần tử nằm ở đầu và cuối của dãy con
  13. // - Nhận xét: để dãy con thoả mãn thì ta chỉ cần a[beg] <= a[last], còn các phần tử nằm giữa beg và last không quan trọng
  14. //   => Gọi số phần tử nằm giữa beg và last là cnt => cnt = last - beg - 1
  15. //   => Khi đó ta có 2^cnt cách chọn các phần tử nằm giữa beg và last trong dãy con
  16. // - Phân tích 2^cnt = 2^(last - beg - 1) = 2^last / 2^(beg + 1)
  17. // => Với mỗi last, đặt sum_beg = tổng các 1 / 2^(beg + 1) (với beg < last và a[beg] <= a[last])
  18. // => ans += 2^last * sum_beg
  19. // => Việc tính nhanh sum_beg có thể dùng Fenwick Tree / Segment Tree
  20. // => O(nlogn)
  21. const int N = 3e5 + 5; 
  22. const int MOD = 998244353; 
  23.  
  24. int n; 
  25. int a[N]; 
  26. int pow2[N]; // pow2[i] = 2^i % MOD 
  27. int inv_pow2[N]; // inv_pow2[i] = Nghịch đảo modulo của 2^i
  28.  
  29. void compress(int a[]) {
  30. 	vector<int> vals; 
  31. 	for (int i = 1; i <= n; i++) vals.push_back(a[i]); 
  32. 	sort(vals.begin(), vals.end()); 
  33. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  34. 	for (int i = 1; i <= n; i++) {
  35. 		a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1; 
  36. 	}
  37. }
  38.  
  39. void add(int& a, int b) {
  40. 	a += b; 
  41. 	if (a >= MOD) a -= MOD; 
  42. }
  43.  
  44. int binpow(int a, int b) {
  45. 	int ans = 1; 
  46. 	for (; b > 0; b >>= 1) {
  47. 		if (b & 1) ans = 1ll * ans * a % MOD; 
  48. 		a = 1ll * a * a % MOD; 
  49. 	}	
  50. 	return ans; 
  51. }
  52.  
  53. struct Fenwick {
  54. 	int n; 
  55. 	vector<int> ft;
  56.  
  57. 	Fenwick(int n) : n(n) {
  58. 		ft.resize(n, 0); 
  59. 	} 	
  60.  
  61. 	void update(int pos, int val) {
  62. 		for (; pos < n; pos += pos & (-pos)) {
  63. 			add(ft[pos], val); 
  64. 		}
  65. 	}
  66.  
  67. 	int get(int pos) {
  68. 		int ans = 0;  
  69. 		for (; pos > 0; pos -= pos & (-pos)) {
  70. 			add(ans, ft[pos]); 
  71. 		}
  72. 		return ans; 
  73. 	}
  74. }; 
  75.  
  76. int main() {
  77. 	ios::sync_with_stdio(false); 
  78. 	cin.tie(nullptr); 	
  79. 	cin >> n; 
  80. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  81. 	compress(a); 
  82.  
  83. 	pow2[0] = 1; 
  84. 	for (int i = 1; i <= n; i++) {
  85. 		pow2[i] = 2ll * pow2[i - 1] % MOD; 
  86. 	}	
  87. 	inv_pow2[n] = binpow(pow2[n], MOD - 2); 
  88. 	for (int i = n - 1; i >= 0; i--) {
  89. 		inv_pow2[i] = 2ll * inv_pow2[i + 1] % MOD; 
  90. 	}
  91. 	// int ans = 0; 
  92. 	// for (int last = 1; last <= n; last++) {
  93. 		// for (int beg = 1; beg < last; beg++) {
  94. 			// if (a[beg] <= a[last]) {
  95. 				// add(ans, pow2[last - beg - 1]); 
  96. 			// }
  97. 		// }
  98. 	// } // O(n^2)
  99.  
  100. 	int ans = 0;  
  101. 	Fenwick fenw(n + 1); 
  102. 	for (int last = 1; last <= n; last++) {
  103. 		add(ans, 1ll * pow2[last] * fenw.get(a[last]) % MOD); 
  104. 		fenw.update(a[last], inv_pow2[last + 1]); 
  105. 	} // O(nlogn)
  106.  
  107. 	cout << ans << '\n'; 
  108. }
Success #stdin #stdout 0s 5652KB
comments (?)
stdin
copy 
3
1 2 1
stdout
copy 
3
https://ideone.com/ibBmvB
language:
C++14 (gcc 8.3)
created:
158 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!