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 = 3e4 + 5; 
  11. const int MAX_A = 1e4; 
  12. const int B = 631; // sqrt(N * log2(MAX_A))
  13. const int K = 48; 
  14.  
  15. int n, q; 
  16. int a[N]; 
  17.  
  18. struct fenwick {
  19. 	int n;  
  20. 	vector<int> ft; 
  21.  
  22. 	fenwick() {}
  23.  
  24. 	fenwick(int n): n(n) {
  25. 		ft.resize(n, 0); 
  26. 	}
  27.  
  28. 	void update(int pos, int val) {
  29. 		for (; pos > 0; pos -= pos & (-pos)) ft[pos] += val; 
  30. 	}
  31.  
  32. 	int get(int pos) {
  33. 		int ans = 0;  
  34. 		for (; pos < n; pos += pos & (-pos)) ans += ft[pos]; 
  35. 		return ans; 
  36. 	}
  37. }; 
  38.  
  39. int id[N], L[K], R[K]; 
  40. fenwick BIT[K]; // chi phí bộ nhớ: O(K * MAX_A)
  41. 				// BIT[id] là cây BIT quản lí các phần tử thuộc block id
  42.  
  43. void build() {
  44. 	for (int i = 0; i < K; i++) {
  45. 		L[i] = R[i] = -1;  
  46. 		BIT[i] = fenwick(MAX_A + 1); 
  47. 	}
  48.  
  49. 	for (int i = 1; i <= n; i++) {
  50. 		id[i] = i / B;  
  51. 		if (L[id[i]] == -1) L[id[i]] = i;  
  52. 		R[id[i]] = i;  
  53. 		BIT[id[i]].update(a[i], 1); 
  54. 	}
  55. }
  56.  
  57. int main() {
  58. 	ios::sync_with_stdio(0); cin.tie(0);  	
  59. 	cin >> n;
  60. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  61.  
  62. 	build(); // O(n * log2(MAX_A))
  63.  
  64. 	cin >> q;  
  65.  
  66. 	while (q--) {
  67. 		int type; cin >> type; 
  68.  
  69. 		if (type == 0) {
  70. 			// O(log2(MAX_A))
  71. 			int pos, val; 
  72. 			cin >> pos >> val; 
  73. 			BIT[id[pos]].update(a[pos], -1); 
  74. 			a[pos] = val; 
  75. 			BIT[id[pos]].update(a[pos], 1); 
  76. 		}
  77. 		else {
  78. 			int l, r, k; 
  79. 			cin >> l >> r >> k; 
  80.  
  81. 			int ans = 0;   
  82. 			if (id[l] == id[r]) {
  83. 				for (int i = l; i <= r; i++) ans += (a[i] > k); // O(B)
  84. 			}
  85. 			else {
  86. 				for (int i = l; i <= R[id[l]]; i++) ans += (a[i] > k); // O(B)
  87. 				for (int cid = id[l] + 1; cid <= id[r] - 1; cid++) ans += BIT[cid].get(k + 1); // O(N / B * log2(MAX_A))
  88. 				for (int i = L[id[r]]; i <= r; i++) ans += (a[i] > k); // O(B)
  89. 			}
  90.  
  91. 			cout << ans << '\n'; 
  92. 		}
  93. 	}
  94. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
stdout
copy 
2
1
2
https://ideone.com/Fkwg9h
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!