自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 23:15:54，当前版本为作者最后更新于2025-05-27 11:32:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很少能见到有耐心学会逻辑链这么长并且自然的题，写篇题解纪念一下。

qoj 传送门

发现各种 dp 都需要记录许多状态，主要原因是同时维护两个方向的操作情况实在太复杂，考虑能不能简化一下。发现所有向右走的操作一定在所有向左走的操作的左边，否则交换两者严格更优。

所以现在其实就是要找到一个分界点，左边的操作都选择向右，右边的都向左，发现跨分界点的贡献只和两边操作的总次数有关，如果枚举分界点和两边的操作次数就可以验证。

发现复杂度还是过高，可以先二分答案 $ans$，然后两边的次数分配就只有 $O(ans) = O(m)$ 种方式。考虑能不能把分界点的枚举也省去，以左边为例，发现此时如果确定了右边的操作次数，那么左边能保持合法的最长前缀是可以求出的，假如求出了每种右边次数对应的最长前缀和达到后剩下的次数，那么右边后缀的情况也是同理，只需要翻转序列使用类似算法即可，那么枚举分配方案后就可以通过比较两个前后缀的位置关系直接判定是否可行而无需枚举分界点。

这里需要注意前后缀刚好接上的时候需要特殊考虑，因为前面的结论实际上没有将两类操作完全分开，是可以存在中间的一个位置上同时进行过两种操作的，对于这种情况需要对两边剩下的次数进行讨论，看能否满足共用位置的限制，更详细的可以看 qoj 上的题解中的描述。

考虑加速求出它们的过程。以求出左边的最长前缀为例，设右边操作了 $k$ 次，最长可以满足到 $[1,f_k - 1]$，并剩下 $g_k$ 次操作。那么求解的过程即为依次考虑 $i = 1 \rightarrow n$，并记录现在需要的操作总次数 $x = k$：

• 若 $a_i \le x$，不需要任何操作。
• 否则，若 $x + \lceil \dfrac {x-a_i}{c+1} \rceil \le ans$，则 $x \leftarrow x + \lceil \dfrac {x-a_i}{c+1} \rceil$。
• 否则，$f_k \leftarrow i$，$g_k \leftarrow ans - x$，退出。

如果到最后 $f_k,g_k$ 都没被赋值，那么 $f_k = n+1$。

那么考虑这个过程能否加速维护，即对所有的 $k \in [0,ans]$ 一起维护这个过程，维护每一个 $x_k$ 为对应 $k$ 的 $x$ 值，那么还是上面的过程，初始有 $x_k = k$，每次会对每个 $k$ 进行 $x_k \leftarrow x_k + \lceil \dfrac {\max(0,x_k-a_i)}{c+1} \rceil$，发现后面增加的那个式子在 $x_k$ 增加 $1$ 时至多增加 $1$，因此可以归纳发现 $x$ 数组一直满足 $x_k \le x_{k+1} \le x_k + 1$。

因此转而维护 $x$ 的连续段，维护一个 $x_0$ 和一个位置数组 $a_1 < a_2 < \cdots < a_p$，为 $x$ 数组满足 $x_k = x_{k-1} + 1$ 的 $k$ 的位置，初始 $p = ans + 1$，$a_i = i$，注意最后有一个超出上界的位置以记录 $x$ 数组的结尾。

那么每次的操作为：

• 若 $x_0 \ge a_i$，不需要操作。
• 设 $y = \lceil \dfrac {x_0-a_i}{c+1} \rceil$，并利用上面相除的余数可以找到第一个 $x$ 值是 $c+1$ 的倍数的对应位置 $a_q$，那么 $\forall j \in [0,y)$，删除 $a_{q + (c+1)j}$，如果这个位置已经超出了 $p$ 的范围，那么对 $[a_{p-1},a_p)$ 更新 $f_* = i,g_* = ans - x_0 + p - 1$ 并删除最后一个元素，最后 $x_0 \leftarrow x_0 + y$。

实现时注意应该先算出需要删除多少次最后一个元素并先删除更新答案再做前面的普通删除，否则可能会因前面的删除而影响更新答案的区间情况，在 $a$ 数组删完时及时退出。

qoj 上官方题解说由于每次都是隔 $O(c)$ 个删一个所以每次删除后暴力更新 $a$ 数组是 $O(mc)$ 的，不懂，感觉有可能一次删除只删去了前面的一小部分，但这里使用数据结构维护并不难，发现 $a$ 数组需要做的就是删去某个元素和查询排名为 $a$ 的数，使用平衡树或权值线段树即可维护，可以用树状数组维护对应的权值线段树，这样常数小。

设 $n,m$ 同阶，此时单次 check 的复杂度是 $O(n \log n)$ 的，因此总复杂度为 $O(n \log^2 n)$，无法通过，但继续观察刚才维护的过程，发现 $ans$ 对 $a$ 数组的变化的影响并不大，$ans$ 只影响被删除的后缀情况，因此可以考虑将计算到每个 $i$ 时发生的删除位置都预处理出来，然后每次 check 的时候就相当于只需要维护删除一个数和查询最后一个数，因为每次还需要重新考虑从最后删除并更新答案的情况，那么这个只需要给值域开一个并查集就可以了，以此平衡到 $O(n \log n)$。

代码看 qoj。