fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
7
4
4
3
3
4
3
0
1
https://ideone.com/GojTGD
language:
C++14 (gcc 8.3)
created:
198 days 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!