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. const int Q = 2e5 + 5; 
  12.  
  13. struct query {
  14. 	char type; 
  15. 	int a, b; 
  16. }; 
  17.  
  18. struct fenwick {
  19. 	int n;  
  20. 	vector<int> ft;  
  21.  
  22. 	fenwick(int n) : n(n) {
  23. 		ft.resize(n, 0); 
  24. 	}	
  25.  
  26. 	void update(int pos, int val) {
  27. 		for (; pos < n; pos = pos | (pos + 1)) ft[pos] += val; 
  28. 	}
  29.  
  30. 	int get(int pos) {
  31. 		int ans = 0;  
  32. 		for (; pos >= 0; pos = (pos & (pos + 1)) - 1) ans += ft[pos]; 
  33. 		return ans; 
  34. 	}
  35. }; 
  36.  
  37. int n, q;  
  38. int p[N];
  39. query queries[Q];
  40.  
  41. int sz;  
  42. vector<int> vals; // danh sách các giá trị cần nén
  43.  
  44. int getVal(int x) {
  45. 	return lower_bound(vals.begin(), vals.end(), x) - vals.begin(); 
  46. }
  47.  
  48. int main() {
  49. 	ios::sync_with_stdio(0); cin.tie(0);  	
  50. 	cin >> n >> q; 
  51. 	for (int i = 1; i <= n; i++) cin >> p[i]; 
  52.  
  53. 	for (int i = 1; i <= n; i++) vals.push_back(p[i]); 
  54.  
  55. 	for (int i = 1; i <= q; i++) {
  56. 		char type; cin >> type;  
  57.  
  58. 		if (type == '!') {
  59. 			int pos, x; 
  60. 			cin >> pos >> x;  
  61. 			vals.push_back(x); 
  62. 			queries[i] = {type, pos, x}; 
  63. 		}
  64. 		else {
  65. 			int l, r; 
  66. 			cin >> l >> r; 
  67. 			vals.push_back(l); vals.push_back(r); 
  68. 			queries[i] = {type, l, r}; 
  69. 		}
  70. 	}	
  71.  
  72. 	sort(vals.begin(), vals.end()); 
  73. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  74. 	sz = vals.size();   
  75.  
  76. 	fenwick BIT(sz);  
  77. 	for (int i = 1; i <= n; i++) {
  78. 		p[i] = getVal(p[i]); 
  79. 		BIT.update(p[i], 1); 
  80. 	}
  81.  
  82. 	for (int i = 1; i <= q; i++) {
  83. 		char type = queries[i].type; 
  84.  
  85. 		if (type == '!') {
  86. 			int pos = queries[i].a, x = queries[i].b; 
  87. 			BIT.update(p[pos], -1); 
  88. 			p[pos] = getVal(x);   
  89. 			BIT.update(p[pos], 1); 
  90. 		}
  91. 		else {
  92. 			int l = queries[i].a, r = queries[i].b; 
  93. 			l = getVal(l), r = getVal(r); 
  94. 			int ans = BIT.get(r) - BIT.get(l - 1); 
  95. 			cout << ans << '\n'; 
  96. 		}
  97. 	}
  98. }
  99.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
copy 
3
2
https://ideone.com/wVOedy
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!