F. Machine Learning
思路：
统计每个数字出现的次数numi，记录次数numi出现的次数cnti。
然后就是带修莫队的事情了。
代码：
（注意：不要用Node(x,y,z)这种方式，不然就是错，很迷。）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<cmath> using namespace std; const int maxn = 2e5+10; const double IO = 2.0/3.0; typedef long long LL; int Ki[maxn]={0},l = 1,r = 0,m,n,Ans[maxn] = {0},a[maxn]={0},now[maxn]={0},num[maxn]={0},cnt[maxn]={0},tot = 0; map <int,int> mp; int f(int x){ if(!mp.count(x)){ mp[x] = ++tot; } return mp[x]; } struct N1{ int l,r,id,tim; }qu[maxn]; struct N2{ int pos,nxt,pre; }ca[maxn]; bool cmp(N1 a,N1 b){ if(Ki[a.l]==Ki[b.l]){ if(Ki[a.r]==Ki[b.r]) return a.tim<b.tim; return a.r<b.r; } return a.l<b.l; } int tran(){ for(int i=1;1;i++) if(cnt[i]==0){ return i; } } void Add(int x,int d){ if(num[x]>0) cnt[num[x]]--;//删除上一次的记录 num[x]+=d; if(num[x]>0) cnt[num[x]]++;//记录最新的次数出现的次数 } void Go(int x,int d){ if(l<=x&&x<=r){ Add(a[x],-1); Add(d,1); } a[x] = d; } int main(void){ mp.clear(); scanf("%d%d",&n,&m); int unit = (int)pow(n,IO); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); a[i] = now[i] = f(x);Ki[i] = i/unit+1; } int t1 = 0,t2 = 0; for(int i=1;i<=m;i++){ int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1){ qu[++t1] = N1{x,y,t1,t2}; }else{ y = f(y); ca[++t2] = N2{x,y,now[x]};now[x] = y; } } sort(qu+1,qu+1+t1,cmp); int T = 0; for(int i=1;i<=t1;i++){ while(T<qu[i].tim){ Go(ca[T+1].pos,ca[T+1].nxt);T++; } while(T>qu[i].tim){ Go(ca[T].pos,ca[T].pre);T--; } while(l<qu[i].l){ Add(a[l],-1);l++; } while(l>qu[i].l){ Add(a[l-1],1);l--; } while(r<qu[i].r){ Add(a[r+1],1);r++; } while(r>qu[i].r){ Add(a[r],-1);r--; } Ans[qu[i].id] = tran(); } for(int i=1;i<=t1;i++) printf("%d\n",Ans[i]); return 0; }
