Solution-CF1870G

· · 题解

对于 |S|=1 的情况，答案是 \max(1,S_1)。

对于 |S|>1 的情况，相当于我们要使 S 的 \text{mex} 尽可能大，使得最后一次操作的结果最大。S 中一部分数不会改变，一部分数会先变成 0 然后叠出新的数。不妨考虑判断答案是否 \geq t，这样 \geq t 的数显然都会先执行一次操作变成 0，只需要讨论 \leq t 的数能否把 [0,t-1] 的所有数都叠出来就可以了。

考虑如下过程：初始令 cnt_i 为 i 的出现次数（\geq t 的数看做 0），遍历 i:t-1\to 0，如果 cnt_i<1，则对 j\in [0,i-1] 执行 cnt_j\gets cnt_j-(1-cnt_i) 表示需要提出 1-cnt_i 个数来满足 i 的需求；否则 cnt_i\geq 1，那么令 cnt_0\gets cnt_0+cnt_i-1，表示多余的数用来填补 0 的个数。最后的判断条件为 cnt_0\geq 1。

套用上面的判断方法，动态增加 \text{mex} 并判断可以做到 \mathcal{O}(n^2)。

考虑优化上面的过程，先写出形式化的条件，设 d 表示一个前缀减的标记，z 表示补 0 的个数：

使用数据结构难以维护（分块维护分段函数应该可以 \mathcal{O}(n\sqrt{n}\log n)，但是不太能过），考虑更为简洁的方法。此类数据结构问题的套路是：对于一部分操作，可以平凡解决，另一部分操作次数不多，可以暴力解决。我们证明合法条件下，第一种操作的有效次数是不超过 \sqrt{n} 的。注意到如果在 i 处执行第一种操作，\sum cnt_j 减少至少 i，而当 \sum cnt_j<0 的时候，显然不合法。由于 i 两两不同，且 \sum cnt_i=n，所以根据经典结论，满足 \sum S_i\leq n 的不可重集 S 的大小至多为 \sqrt{n}，可以知道操作次数是不超过 \sqrt{n} 的。

此时需要找到某个前缀中最后一个满足 cnt_i-1<d 的位置，可以使用线段树二分，z 的维护是简单的区间求和，使用线段树可以做到 \mathcal{O}(n\sqrt{n}\log n)。

这个做法经过常数优化之后仍然难以通过，所以需要消 \log。下面给出一种基于在线段树上 dfs 的消 \log 的方法（下文中令 mn_k 表示区间 cnt_i-1 的最小值，sum_k 表示区间 cnt_i-1 的和）：

注意在线段树上任意撒 \sqrt{n} 个点上面的算法可以被卡到 \frac{1}{2}\sqrt{n}\log n 次操作，构造方法如下：考虑长度为 2^{2t} 的线段树，在所有大小为 2^t 的区间节点下面每个点挂一个叶子，那么虚树大小就是 t2^t 的。证明复杂度为 n\sqrt{n} 需要用到本题的性质。考虑所有大小为 2^k 的区间对应的结点中有多少个会被经过，那么对于从左到右第 x 个节点，若它的子树中有至少一个关键点，那么 \sum cnt_j 会至少减少 x2^k，所以不同的 x 为 \sqrt{\dfrac{n}{2^k}} 种。对其求和可得 \sum \sqrt{\dfrac{n}{2^k}}=\sqrt{n}。

总时间复杂度为 \mathcal{O}(n\sqrt{n})。code