题解 CF940F 【Machine Learning】
ouuan
2018-09-30 18:02:31
其实这题根本不用把数字也分块..
如果不会带修莫队的话可以到网上找教程，也可以看[我写的教程](https://www.cnblogs.com/ouuan/p/MoDuiTutorial.html)
首先将数列中原本的数字以及所有修改中的数字全部离散化，然后就是普通的带修莫队，不同之处在于更新答案时不是记录某个数字出现了几次，而是在更新数字出现的次数的同时更新“数字出现的次数”出现的次数，即：
```
void add(int x)
{
--tot[cnt[x]];
++tot[++cnt[x]];
}
void del(int x)
{
--tot[cnt[x]];
++tot[--cnt[x]];
}
```
然后是为什么可以暴力求mex：
考虑答案为 $x$，那么存在出现了 $1$ 次的数、出现了 $2$ 次的数……出现了 $x-1$ 次的数。所以，$\sum\limits_{i=1}^{x-1}i<=n$，就是说答案是 $O(\sqrt{n})$ 级别的，暴力求解的复杂度为 $O(n\sqrt{n})$，而带修莫队的复杂度为 $O(n^{\frac{5}{3}})$，也就是说暴力求mex完全不影响总复杂度。
所以一行求mex就好了：
```
for (ans[q[i].id]=1;tot[ans[q[i].id]]>0;++ans[q[i].id]);
```
完整代码：
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read()
{
char c;int out=0;
for (c=getchar();c<'0'||c>'9';c=getchar());
for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}
return out;
}
void write(int x)
{
if (x>9){write(x/10);}
putchar(x%10+'0');
}
const int B=2154;
struct Query
{
int l,r,t,id;
bool operator<(Query& y)
{
return l/B==y.l/B?(r/B==y.r/B?t<y.t:r<y.r):l<y.l;
}
} q[100010];
struct Change
{
int p,x;
} c[100010];
void add(int x);
void del(int x);
void modify(int ti,int qu);
int n,m,a[100010],b[200010],cnt[200010],tot[100010],qcnt,ccnt,qaq,now,ans[100010];
int main()
{
int i,j,l=1,r=0,type;
n=read();
m=read();
for (i=1;i<=n;++i)
{
b[qaq++]=a[i]=read();
}
for (i=0;i<m;++i)
{
type=read();
if (type==1)
{
q[++qcnt].l=read();
q[qcnt].r=read();
q[qcnt].t=ccnt;
q[qcnt].id=qcnt;
}
else
{
c[++ccnt].p=read();
b[qaq++]=c[ccnt].x=read();
}
}
sort(b,b+qaq);
qaq=unique(b,b+qaq)-b;
for (i=1;i<=n;++i)
{
a[i]=lower_bound(b,b+qaq,a[i])-b;
}
for (i=1;i<=ccnt;++i)
{
c[i].x=lower_bound(b,b+qaq,c[i].x)-b;
}
sort(q+1,q+qcnt+1);
for (i=1;i<=qcnt;++i)
{
while (l>q[i].l)
{
add(a[--l]);
}
while (r<q[i].r)
{
add(a[++r]);
}
while (l<q[i].l)
{
del(a[l++]);
}
while (r>q[i].r)
{
del(a[r--]);
}
while (now<q[i].t)
{
modify(++now,i);
}
while (now>q[i].t)
{
modify(now--,i);
}
for (ans[q[i].id]=1;tot[ans[q[i].id]]>0;++ans[q[i].id]);
}
for (i=1;i<=qcnt;++i)
{
write(ans[i]);
putchar('\n');
}
return 0;
}
void add(int x)
{
--tot[cnt[x]];
++tot[++cnt[x]];
}
void del(int x)
{
--tot[cnt[x]];
++tot[--cnt[x]];
}
void modify(int ti,int qu)
{
if (c[ti].p>=q[qu].l&&c[ti].p<=q[qu].r)
{
del(a[c[ti].p]);
add(c[ti].x);
}
swap(c[ti].x,a[c[ti].p]);
}
```