题解：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 指出一处笔误，已修正。