复杂度对的啊
对值域分块 更新是$O(1)$的更新$O(n\sqrt n)$次 查询是$O(\sqrt n)$的 总共还是$O(n\sqrt n)$的
by Mr_Spade @ 2018-12-29 09:22:50
@[Mr_Spade](/space/show?uid=7253) 大概我没有说清楚，我说的莫队并不是对值域分块，是题解中那种近似于暴力的莫队。
```
用一个mn作为每次转移的答案,add操作就从mn开始找到第一个没有出现的数,del操作,如果减的那个数a[x]等于0,mn=Min(mn,a[x]).
```
by Taduro @ 2018-12-29 09:26:12
@[多弗桃](/space/show?uid=63661) 那不知道...听上去很不靠谱 如果是暴力找的话感觉不对吧...
by Mr_Spade @ 2018-12-29 09:28:10
@[Mr_Spade](/space/show?uid=7253) 所以能过就是因为数据水吧。。。。
by Taduro @ 2018-12-29 09:40:22
@[多弗桃](/space/show?uid=63661) @[Mr_Spade](/space/show?uid=7253) 暴力是对的，可以参考[我的博客](https://ouuan.blog.luogu.org/solution-cf940f)，那道题是带修的，复杂度证明类似。
by ouuan @ 2018-12-29 10:38:13
> 考虑答案为 $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完全不影响总复杂度。
上面摘自CF940F我的题解。
不带修莫队复杂度为 $O(m\log m+n\sqrt m)$ ，暴力求解复杂度为 $O(m\sqrt n)$，总复杂度为 $O(m\log m+n\sqrt m+m\sqrt n)$
by ouuan @ 2018-12-29 10:42:01
至于莫队复杂度证明，也可以看[我写的教程](https://ouuan.github.io/%E8%8E%AB%E9%98%9F%E3%80%81%E5%B8%A6%E4%BF%AE%E8%8E%AB%E9%98%9F%E3%80%81%E6%A0%91%E4%B8%8A%E8%8E%AB%E9%98%9F%E8%AF%A6%E8%A7%A3/)
by ouuan @ 2018-12-29 10:44:43
@[ouuan](/space/show?uid=49742)
orz神仙！！！
但我并没有看懂您的题解。。。而且我认为这两题是不一样的。
本题是求mex，数字的值域为$[0,1e9]$，但因为大于 $n$ 的数没有意义，所以值域可以看成$[0,n]$。最坏情况下答案为：查询区间长度+1。
而CF那题是求出现次数的mex，值域为$[0,\text{查询区间的大小}]$，也可以看为$[0,n]$。但实际上，如果是最坏情况的话，设答案为x，则有：
$$1+2+3...+x=\frac{x*(x-1)}{2}=n$$
$x$在$\sqrt{n}$级别。
另外，我尝试魔改您的代码以测试这题的hack数据，但因为本地没有c++11编译器以及看不懂您的码风而失败了，如果您认为我上面的说法有问题而又想不出什么说法来使我这个蒟蒻明白的话，可以测试一下本题讨论帖中的hack数据来打我的脸。
by Taduro @ 2018-12-29 11:31:45
@[多弗桃](/space/show?uid=63661) 哦，我没仔细看题..那这题可能不能暴力求
by ouuan @ 2018-12-29 11:36:36
我再仔细看看题...说不定能证？
by ouuan @ 2018-12-29 11:38:02