题解：CF2049F MEX OR Mania

· · 题解

提供一种题解区没有的做法。

首先还是要注意到 \mathrm{mex}\le \max+1,\mathrm{or}\ge \max，所以题目条件成立就要这两个同时取等。所以好的序列一定是只出现 [0,2^k-1] 里的数且每个数都要出现一次。

因为 CF 的题如果是 O(n\log n) 应该会开 2\times 10^5，所以大胆猜测这题是 O(n\log^2n)。于是可以做一些奔放的操作。

先想想一次询问怎么做。考虑枚举 k，然后判断是否可行。（注意不能二分，因为可行性不具有单调性）如何判断是否可行？把所有 \ge 2^k 的数视作 "阻隔点"，由此隔出若干个段。我们对每个段判断是否合法，从合法的里面取最大长度即可。

如果拓展到多次询问，如果每次都枚举 k 然后 \ge O(n) 的时间判定，复杂度是 O(qn\log n) 往上的，考虑优化。

因为题目的修改只有单点，意味着合法段的变化量不会太大。于是尝试用数据结构对每个 k 维护当前所有合法段长度，只需要在修改时维护一两个合法段的变化。这样就可以省去 O(n) 检验的复杂度。使用 multiset 可以完成。
（另一种理解方式就是拆 \log n 个数组出来，每个数组用一个 multiset 维护答案）

查询已经做完了，就是枚举所有 multiset 求最大值。然后下一个问题是怎么快速做修改。

因为合法段之间是相对独立的，所以很难对一整个数组维护一个整体的东西来处理，于是考虑对每个合法段都维护一个数据结构快速处理修改。

（然后我在这里卡了半个钟没想到 map …… 不过搞出另一个更朴素的东西）

注意到合法段的长度必然 \ge 2^k，所以合法段的数量不会太多。对于一个固定的 k，其合法段的数量是 \le [\dfrac{n}{2^k}] 的；同时，每个合法段只需要记录 0\sim 2^k-1 的出现情况即可。因此，我们对每个长度 \ge 2^k 的段直接维护一个 cnt[0\sim 2^k-1] 的数组，这样复杂度仍然是 O(\sum [\dfrac{n}{2^i}]\cdot 2^i)=O(n\log n) 的。

处理修改就使用启发式分裂可以做，有题解说过了，这里不再赘述。

upd：pp_orange 指出一处笔误，已修正。