fork download
  1. #include<bits/stdc++.h>
  2. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  3. using namespace std;
  4. #define int long long
  5.  
  6. class SegTree{
  7. vector<int>seg;
  8. public:
  9. vector<int>index;
  10. SegTree(int n){
  11. seg.resize(4*n+1);
  12. }
  13. void build(int ind, int low, int high, vector<int>&buckets){
  14. if(low==high){
  15. seg[ind] = buckets[low];
  16. return;
  17. }
  18. int mid = low+ ((high-low)>>1);
  19. build(2*ind+1, low, mid, buckets);
  20. build(2*ind+2, mid+1, high, buckets);
  21. seg[ind] = seg[2*ind+1] + seg[2*ind+2];
  22. }
  23.  
  24. int query(int ind, int low, int high, int l, int r){
  25. if(high<l || low>r) return 0;
  26. if(low>=l && high<=r) return seg[ind];
  27. int mid = low+ ((high-low)>>1);
  28. return query(2*ind+1,low,mid,l,r) + query(2*ind+2,mid+1,high,l,r);
  29. }
  30.  
  31. void update(int ind, int low,int high, int key,int val){
  32. if(low==high){
  33. seg[ind] = val;
  34. return;
  35. }
  36. int mid = (low+high)/2;
  37. if(key<=mid) update(2*ind+1,low,mid,key,val);
  38. else update(2*ind+2,mid+1,high,key,val);
  39. seg[ind] = seg[2*ind+1] + seg[2*ind+2];
  40. }
  41.  
  42. };
  43.  
  44. int buck_no(int x){
  45. if(x%100==0) x--;
  46. return x/100;
  47. }
  48.  
  49. int calc(int lo,map<int,int>&mp,int hi){
  50. int ans = 0;
  51. for(int i=lo;i<=hi;i++){
  52. ans+=mp[i];
  53. }
  54. return ans;
  55. }
  56.  
  57. void solve(){
  58. int n,q; cin>>n>>q;
  59. vector<int>a(n);
  60. map<int,int>mp;
  61. vector<int>buckets(10000000);
  62. for(int i=0;i<n;i++) {
  63. cin>>a[i];
  64. mp[a[i]]++;
  65. buckets[buck_no(a[i])]++;
  66. }
  67. SegTree sg(10000000);
  68. sg.build(0,0,10000000,buckets);
  69.  
  70. for(int i=0;i<q;i++){
  71. char op; cin>>op;
  72. int x,y; cin>>x>>y;
  73. if(op=='?'){
  74. int ans = calc(x,mp,min(y,(buck_no(x)+1)*100));
  75. if(buck_no(x)!=buck_no(y)) {
  76. ans+=calc(max(x,buck_no(y)*100+1),mp,y);
  77. }
  78. ans += sg.query(0,0,10000000,buck_no(x)+1,buck_no(y)-1);
  79. cout<<ans<<endl;
  80. }
  81. else {
  82. sg.update(0,0,10000000,buck_no(a[x-1]),--buckets[buck_no(a[x-1])]);
  83. sg.update(0,0,10000000,buck_no(y),++buckets[buck_no(y)]);
  84. mp[a[x-1]]--; mp[y]++;
  85. a[x-1] = y;
  86. }
  87. }
  88. }
  89. signed main(){
  90. solve();
  91. cout<<endl;
  92. }
Success #stdin #stdout 0.14s 393756KB
stdin
10 10
9 9 1 4 3 2 10 1 2 1
? 1 5
? 3 9
? 2 5
! 5 1
? 2 5
? 2 4
? 3 10
? 2 6
? 7 7
? 3 7
stdout
7
4
4
3
3
4
3
0
1