fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const int MX = 4e5 + 5;
  7.  
  8. ll bit[MX];
  9. vector<int> vals;
  10. int n, q;
  11.  
  12. void upd(int i, int val) {
  13. 	for (; i <= MX; i += i & (-i)) { bit[i] += val; }
  14. }
  15.  
  16. void ad(int x, int b) {
  17. 	int ind = upper_bound(vals.begin(), vals.end(), x) - vals.begin();
  18. 	upd(ind, b);
  19. }
  20.  
  21. ll sum(int x) {
  22. 	ll res = 0;
  23. 	for (; x; x -= x & (-x)) { res += bit[x]; }
  24. 	return res;
  25. }
  26.  
  27. ll query(int x) {
  28. 	int ind = upper_bound(vals.begin(), vals.end(), x) - vals.begin();
  29. 	return sum(ind);
  30. }
  31.  
  32. int main() {
  33. 	cin >> n >> q;
  34. 	vector<int> ar(n);
  35. 	for (int i = 0; i < n; i++) { cin >> ar[i]; }
  36. 	vals = ar;
  37. 	vector<array<int, 3>> rec;
  38. 	for (int i = 0; i < q; i++) {
  39. 		char t;
  40. 		int a, b;
  41. 		cin >> t >> a >> b;
  42. 		rec.push_back({t == '?', a, b});
  43. 		if (t == '!') vals.push_back(b);
  44. 	}
  45. 	sort(vals.begin(), vals.end());
  46. 	vals.erase(unique(vals.begin(), vals.end()), vals.end());
  47. 	for (int i = 0; i < n; i++) { ad(ar[i], 1); }
  48. 	for (auto u : rec) {
  49. 		u[1]--;
  50. 		if (u[0] == 0) {
  51. 			ad(ar[u[1]], -1);
  52. 			ar[u[1]] = u[2];
  53. 			ad(ar[u[1]], 1);
  54. 		} else {
  55. 			cout << query(u[2]) - query(u[1]) << '\n';
  56. 		}
  57. 	}
  58. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
copy 
3
2
https://ideone.com/R9qMdQ
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!