fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main() {
  7. 	cin.tie(0);
  8. 	ios_base::sync_with_stdio(0);
  9.  
  10. 	int n, q;
  11. 	cin >> n >> q;
  12. 	vector<int> p(n);
  13. 	vector<tuple<char, int, int>> queries;
  14. 	vector<int> val_set;
  15.  
  16. 	for(int i = 0; i < n; i++){
  17. 		cin >> p[i];
  18. 		val_set.push_back(p[i]);
  19. 	}
  20.  
  21. 	for(int i = 0; i < q; i++){
  22. 		char op;
  23. 		int a, b;
  24. 		cin >> op >> a >> b;
  25. 		if(op == '?') val_set.push_back(a);
  26. 		else a--;
  27. 		val_set.push_back(b);
  28. 		queries.push_back({op, a, b});
  29. 	}
  30.  
  31. 	sort(val_set.begin(), val_set.end());
  32. 	val_set.resize(unique(val_set.begin(), val_set.end()) - val_set.begin());
  33.  
  34. 	for(auto &p_val: p){
  35. 		p_val = lower_bound(val_set.begin(), val_set.end(), p_val) - val_set.begin();
  36. 	}
  37. 	for(auto &[op, a, b]: queries){
  38. 		if(op == '?') a = lower_bound(val_set.begin(), val_set.end(), a) - val_set.begin();
  39. 		b = lower_bound(val_set.begin(), val_set.end(), b) - val_set.begin();
  40. 	}
  41.  
  42. 	vector<int> BITS(val_set.size() + 1);
  43. 	auto update = [&BITS](int pos, int val){
  44. 		while(pos < BITS.size()){
  45. 			BITS[pos] += val;
  46. 			pos += pos & -pos;
  47. 		}
  48. 	};
  49. 	auto query = [&BITS](int pos){
  50. 		int ans = 0;
  51. 		while(pos){
  52. 			ans += BITS[pos];
  53. 			pos -= pos & -pos;
  54. 		}
  55. 		return ans;
  56. 	};
  57.  
  58. 	for(auto &p_val: p){
  59. 		update(p_val + 1, 1);
  60. 	}
  61.  
  62. 	for(auto &[op, a, b]: queries){
  63. 		if(op == '?') cout << query(b + 1) - query(a) << '\n';
  64. 		else{
  65. 			update(p[a] + 1, -1);
  66. 			p[a] = b;
  67. 			update(p[a] + 1, 1);
  68. 		}
  69. 	}
  70. 	return 0;
  71. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
copy 
3
2
https://ideone.com/ondtwB
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!