SOJ1972 题解

题意

设 \(S\) 为一个可重数集，满足所有元素均为非负整数。你可以对 \(S\) 进行若干次（可以为 \(0\) 次）如下操作：选择一个非负整数 \(x\) 满足 \(x\) 至少在 \(S\) 中出现了 \(2\) 次，在 \(S\) 中删除一个 \(x\)，并将 \((x-1)\) 或 \((x+1)\) 插入 \(S\)。如果你选择插入 \((x-1)\)，你必须保证 \((x-1)\) 非负。记 \(F(S)\) 为通过对 \(S\) 进行若干次如上操作能得到的 \(\operatorname{mex}(S)\) 的最大值。其中 \(\operatorname{mex}(S)\) 表示最小的不属于 \(S\) 的非负整数。

给定一个长度为 \(n\) 的序列 \(a_{1\dots n}\)。有 \(q\) 次询问，每次给出 \(l,r(1\le l\le r\le n)\)。对于每一个询问，你需要回答 \(F(\{a_l,a_{l+1},\dots,a_r\})\)。

\(1\le n,q\le 5\times 10^5,0\le a_i\le 10^9\)。

题解

学习了一种新方法，记之。

先转化一下，\(F(S)\) 即为求最大的 \(x\) 满足 \(S\) 中小于 \(x\) 的数的个数大于等于 \(x-1\)。

考虑区间互不包含时怎么做。将区间按左端点排序，从大到小删除所有数，动态维护每个区间内剩余数的个数。此时删除一个数后改变的区间一定连续，于是容易维护。

对于一般情况，注意到一个性质：如果区间 \([l',r']\) 被 \([l,r]\) 包含，则 \(F(\{a_{l'},\dots,a_{r'}\}) \le F(\{a_l,\dots,a_r\})\)。于是先忽略所有被包含的区间，按照上述算法执行到有区间出现答案。此时将该区间删除，同时需要加入一些新的不被包含的区间。找区间的操作可以线段树二分。

实现精细一点，复杂度 \(O(n\log n)\)。