fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,q,v=0,a[200005],bit[1000006];
  5. pair <char,pair<int,int>> p[200005];
  6. void UPDATE(int i, int V)
  7. {
  8.     while (i<=v) bit[i]+=V,i+=i&(-i);
  9.     return;
  10. }
  11. int GET(int l, int r)
  12. {
  13.     l--;
  14.     int resl=0,resr=0;
  15.     while (l>0) resl+=bit[l],l-=l&(-l);
  16.     while (r>0) resr+=bit[r],r-=r&(-r);
  17.     return resr-resl;
  18. }
  19. void READINPUT()
  20. {
  21.     set <int> se;
  22.     map <int,int> mp;
  23.     cin>>n>>q;
  24.     for (int i=1;i<=n;i++) cin>>a[i],se.insert(a[i]);
  25.     for (int i=1;i<=q;i++)
  26.     {
  27.         cin>>p[i].first>>p[i].second.first>>p[i].second.second;
  28.         if (p[i].first=='!') se.insert(p[i].second.second);
  29.         else se.insert(p[i].second.first),se.insert(p[i].second.second);
  30.     }
  31.     for (int x : se) v++,mp[x]=v;
  32.     for (int i=1;i<=n;i++) a[i]=mp[a[i]];
  33.     for (int i=1;i<=q;i++)
  34.     {
  35.         if (p[i].first=='!') p[i].second.second=mp[p[i].second.second];
  36.         else p[i].second.first=mp[p[i].second.first],p[i].second.second=mp[p[i].second.second];
  37.     }
  38. }
  39. signed main()
  40. {
  41.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  42.     READINPUT();
  43.     for (int i=1;i<=n;i++) UPDATE(a[i],1);
  44.     for (int i=1;i<=q;i++)
  45.     {
  46.         if (p[i].first=='!')
  47.         {
  48.             UPDATE(p[i].second.second,1);
  49.             UPDATE(a[p[i].second.first],-1);
  50.             a[p[i].second.first]=p[i].second.second;
  51.         }
  52.         else cout<<GET(p[i].second.first,p[i].second.second)<<'\n';
  53.     }
  54.     return 0;
  55. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JugXef
language:
C++14 (gcc 8.3)
created:
1 day 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!