Codeforces Round #466 (Div. 2) F. Machine Learning (带修莫队)

本文主要是介绍Codeforces Round #466 (Div. 2) F. Machine Learning (带修莫队)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

一个数组，问某个区间里面，第一个没出现的所有数出现次数的出现次数正整数

思路：

题意有点毒，第二次才读对。一读题就觉得，带修莫队就可以处理了，然后我们发现需要离散化，那么我们干脆在之前就把数字离散了，因为有修改，所以最多为2e5个数，这样就很好处理了。因为是出现次数的出现次数，所以最多只有不到500项，那么暴力从1找就行（我优化了寻找的过程反而不如暴力，果然还是我太菜了ORZ）

错误及反思：

好像CF已经给你能inline的都inline了，所以我加不加inline时间都一样

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 200100;
int n,qus,blocks,block[N],a[N],tid=1,ans[N],num[N],tnum[N],ti=0,k,totq=0,last[N],totc=0;
map<int,int> mp;
struct Q{int l,r,tim,id;
}q[N];bool cmp(Q a,Q b){if(block[a.l]==block[b.l]){if(block[a.r]==block[b.r])return a.tim<b.tim;return a.r<b.r;}return a.l<b.l;
}struct C{int pos,to,bef;
}c[N];void change(int x,int y){tnum[num[x]]--;num[x]+=y;tnum[num[x]]++;
}
int main(){scanf("%d%d",&n,&qus);blocks=pow(n,0.66666);for(int i=1;i<=n;i++){scanf("%d",&a[i]);block[i]=i/blocks+1;if(!mp[a[i]]) mp[a[i]]=tid++;a[i]=mp[a[i]];last[i]=a[i];}for(int i=0;i<qus;i++){scanf("%d",&k);if(k==1){scanf("%d%d",&q[totq].l,&q[totq].r);q[totq].id=totq;q[totq++].tim=totc;}else{scanf("%d%d",&c[totc].pos,&c[totc].to);if(!mp[c[totc].to]) mp[c[totc].to]=tid++;c[totc].to=mp[c[totc].to];c[totc].bef=last[c[totc].pos];last[c[totc].pos]=c[totc++].to;}}sort(q,q+totq,cmp);for(int i=0,l=1,r=0,ti=0;i<totq;i++){for(;ti<q[i].tim;ti++){if(l<=c[ti].pos&&r>=c[ti].pos){change(c[ti].bef,-1);change(c[ti].to,1);}a[c[ti].pos]=c[ti].to;}for(;ti>q[i].tim;ti--){if(l<=c[ti-1].pos&&r>=c[ti-1].pos){change(c[ti-1].bef,1);change(c[ti-1].to,-1);}a[c[ti-1].pos]=c[ti-1].bef;}for(;r<q[i].r;r++)change(a[r+1],1);for(;l>q[i].l;l--)change(a[l-1],1);for(;r>q[i].r;r--)change(a[r],-1);for(;l<q[i].l;l++)change(a[l],-1);ans[q[i].id]=1;while(tnum[ans[q[i].id]]) ans[q[i].id]++;}for(int i=0;i<totq;i++)printf("%d\n",ans[i]);
}