fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN=2e5+1;
  5. int n, q, a[MAXN], type[MAXN], l[MAXN], r[MAXN], cnt=0;
  6. char c;
  7. set<int> s;
  8. map<int, int> mp;
  9.  
  10. struct fenwick_tree{
  11.     int f[3*MAXN];
  12.  
  13.     void update(int pos, int val)
  14.     {
  15.         for (int i=pos; i<=cnt; i+=i&-i){
  16.             f[i]+=val;
  17.         }
  18.     }
  19.  
  20.     int getSum(int pos)
  21.     {
  22.         int res=0;
  23.         for (int i=pos; i>0; i-=i&-i){
  24.             res+=f[i];
  25.         }
  26.         return res;
  27.     }
  28.  
  29.     int query(int l, int r)
  30.     {
  31.         return getSum(r)-getSum(l-1);
  32.     }
  33. }BIT;
  34.  
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(0);
  38.     cin.tie(0); cout.tie(0);
  39.     cin >> n >> q;
  40.     for (int i=1; i<=n; i++){
  41.         cin >> a[i];
  42.         s.insert(a[i]);
  43.     }
  44.     for (int i=1; i<=q; i++){
  45.         cin >> c >> l[i] >> r[i];
  46.         if(c=='?') type[i]=1;
  47.         s.insert(r[i]);
  48.         if(type[i]) s.insert(l[i]);
  49.     }
  50.     for (auto x:s){
  51.         mp[x]=++cnt;
  52.     }
  53.     for (int i=1; i<=n; i++){
  54.         a[i]=mp[a[i]];
  55.         BIT.update(a[i], 1);
  56.     }
  57.     for (int i=1; i<=q; i++){
  58.         if(type[i]){
  59.             cout << BIT.query(mp[l[i]], mp[r[i]]) << "\n";
  60.             continue;
  61.         }
  62.         BIT.update(a[l[i]], -1);
  63.         a[l[i]]=mp[r[i]];
  64.         BIT.update(a[l[i]], 1);
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yIIkwr
language:
C++ (gcc 8.3)
created:
11 hours 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!