fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define ll long long
  5. #define maxn 100005
  6. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7. #define fi first
  8. #define sti string
  9. #define se second
  10.  
  11. using namespace std;
  12.  
  13. const int MAX=500;
  14. int block,a[maxn];
  15. int freq[maxn],cnt[maxn];
  16. int n,q,ans[maxn];
  17.  
  18. struct Update {
  19.    int pos,oldval,newval;
  20. };
  21.  
  22. struct Query {
  23.    int l,r,t,id;
  24.    bool operator < (const Query &other) const {
  25.       int x=l/block; int y=other.l/block;
  26.       int X=r/block; int Y=other.r/block;
  27.       if(x != y) return x < y;
  28.       if(X != Y) return X < Y;
  29.       return t < other.t;
  30.    }
  31. };
  32.  
  33. vector<Update> up;
  34.  
  35. void add(int pos){
  36.    int Val=a[pos];
  37.    int old=freq[Val];
  38.    int New=++freq[Val];
  39.    cnt[old]--;
  40.    cnt[New]++;
  41. }
  42.  
  43. void sub(int pos){
  44.    int Val=a[pos];
  45.    int old=freq[Val];
  46.    int New=--freq[Val];
  47.    cnt[old]--;
  48.    cnt[New]++;
  49. }
  50.  
  51.  
  52. void apply(int t,int L,int R){
  53.    int pos=up[t].pos;
  54.    int old=a[pos];
  55.    int New=up[t].newval;
  56.    if(L<=pos && pos<=R){
  57.       sub(pos);
  58.       a[pos]=New;
  59.       add(pos);
  60.    }
  61.    else a[pos]=New;
  62. }
  63.  
  64. void roll(int t,int L,int R){
  65.    int pos=up[t].pos;
  66.    int old=up[t].oldval;
  67.    int New=a[pos];
  68.    if(L<=pos && pos<=R){
  69.       sub(pos);
  70.       a[pos]=old;
  71.       add(pos);
  72.    }
  73.    else a[pos]=old;
  74. }
  75.  
  76. vector<int> value;
  77.  
  78. int getid(int x){
  79.    return lower_bound(value.begin(),value.end(),x)-value.begin()+1;
  80. }
  81.  
  82. signed main() {
  83.     itachi
  84.     cin>>n>>q;
  85.     for(int i=1;i<=n;i++) {
  86.         cin>>a[i];
  87.         value.push_back(a[i]);
  88.     }
  89.     vector<Query> que;
  90.     for(int i=1;i<=q;i++){
  91.         int opt;
  92.         cin>>opt;
  93.         if(opt==2){
  94.             int pos,x;
  95.             cin>>pos>>x;
  96.             value.push_back(x);
  97.             Update tmp={pos,a[pos],x};
  98.             a[pos]=x;
  99.             up.push_back(tmp);
  100.         }
  101.         else{
  102.             int l,r;
  103.             cin>>l>>r;
  104.             que.push_back({l,r,(int)up.size(),(int)que.size()});
  105.         }
  106.     }
  107.     sort(value.begin(),value.end());
  108.     value.erase(unique(value.begin(),value.end()),value.end());
  109.  
  110.     for(int i=1;i<=n;i++) a[i]=getid(a[i]);
  111.     for(auto &tmp : up){
  112.         tmp.oldval=getid(tmp.oldval);
  113.         tmp.newval=getid(tmp.newval);
  114.     }
  115.     for(int i=(int)up.size()-1;i>=0;i--) a[up[i].pos]=up[i].oldval;
  116.     ll xxx=pow(max(1LL,n),2.0/3.0);
  117.     block=max(1LL,xxx);
  118.     sort(que.begin(),que.end());
  119.     int curL=1,curR=0,curT=0;
  120.     for(auto &tmp : que){
  121.         while(curL > tmp.l) add(--curL);
  122.         while(curR < tmp.r) add(++curR);
  123.         while(curL < tmp.l) sub(curL++);
  124.         while(curR > tmp.r) sub(curR--);
  125.         while(curT < tmp.t) apply(curT++,curL,curR);
  126.         while(curT > tmp.t) roll(--curT,curL,curR);
  127.         int res=MAX+1;
  128.         for(int x=1;x<=MAX;x++){
  129.             if(cnt[x]==0){
  130.                 res=x;
  131.                 break;
  132.             }
  133.         }
  134.         ans[tmp.id]=res;
  135.     }
  136.     for(int i=0;i<que.size();i++) cout<<ans[i]<<'\n';
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZUBFRu
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!