fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define maxn 250005
  6. #define maxv 50010
  7. using namespace std;
  8. ll sz,block_id[maxn],n,a[maxn],q,bit[maxn];
  9. ll ans=0;
  10. vector<int> blocks[605];
  11. void pre(){
  12.    sz=sqrt(n);
  13.    for(int i=1;i<=n;i++){
  14.       block_id[i]=(i-1)/sz;
  15.       blocks[block_id[i]].push_back(a[i]);
  16.    }
  17.    for(int i=0;i<=600;i++){
  18.     sort(blocks[i].begin(),blocks[i].end());
  19.    }
  20. }
  21. void sub(int pos,ll val){
  22.    int id=block_id[pos];
  23.    auto &v = blocks[id];
  24.    auto it=lower_bound(v.begin(),v.end(),val);
  25.    if(it!=v.end()) v.erase(it);
  26. }
  27. void add(int pos,ll val){
  28.    int id=block_id[pos];
  29.    auto &v=blocks[id];
  30.    v.insert(lower_bound(v.begin(), v.end(), val), val);
  31. }
  32. ll cnt_less(int l,int r,ll val){
  33.    if(l>r) return 0;
  34.    ll res=0;
  35.    int bl=block_id[l],br=block_id[r];
  36.    if(bl==br){
  37.       for(int i=l;i<=r;i++) res+=(a[i]<val);
  38.       return res;
  39.    }
  40.    ll end_l=min(n+1,(bl+1)*sz+1);
  41.    for(int i=l;i<end_l;i++) res+=(a[i]<val);
  42.    for (int i = bl + 1; i < br;i++) {
  43.         res += lower_bound(blocks[i].begin(), blocks[i].end(), val) - blocks[i].begin();
  44.     }
  45.     for (ll i = br*sz+1;i<=r;i++) res+=(a[i]<val);
  46.     return res;
  47. }
  48. ll cnt_greater(int l,int r,ll val){
  49.    if(l>r) return 0;
  50.    ll res=0;
  51.    int bl=block_id[l],br=block_id[r];
  52.    if(bl==br){
  53.       for(int i=l;i<=r;i++) res+=(a[i]>val);
  54.       return res;
  55.    }
  56.    ll end_l=min(n+1,(bl+1)*sz+1);
  57.    for(int i=l;i<end_l;i++) res+=(a[i]>val);
  58.    for (int i = bl + 1; i < br;i++) {
  59.         auto it = upper_bound(blocks[i].begin(), blocks[i].end(), val);
  60.         res += blocks[i].end() - it;
  61.     }
  62.     for (ll i = br*sz+1;i<=r;i++) res+=(a[i]>val);
  63.     return res;
  64. }
  65. void update(int pos){
  66.     for(;pos<=maxv;pos+=pos&-pos) bit[pos]++;
  67. }
  68. ll get(int pos){
  69.     ll res=0;
  70.     for(;pos>0;pos-=pos&-pos) res+=bit[pos];
  71.     return res;
  72. }
  73. int main()
  74. {
  75.     itachi
  76.     cin>>n;
  77.     for(int i=1;i<=n;i++) cin>>a[i];
  78.     pre();
  79.     ans=0;
  80.     for(int i=n;i>=1;i--){
  81.         ans+=get(a[i]-1);
  82.         update(a[i]);
  83.     }
  84.     cin>>q;
  85.     while(q--){
  86.         ll x,y; cin>>x>>y;
  87.         ll cur=a[x];
  88.         ans-=cnt_greater(1,x-1,a[x]);
  89.         ans-=cnt_less(x+1,n,a[x]);
  90.         sub(x,cur);
  91.         a[x]=y;
  92.         add(x,y);
  93.         ans+=cnt_greater(1,x-1,a[x]);
  94.         ans+=cnt_less(x+1,n,a[x]);
  95.         cout<<ans<<'\n';
  96.     }
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rVYRwu
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!