自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:44:21，当前版本为作者最后更新于2024-03-13 22:38:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑若原来的序列是不降的，那么进行 $1$ 操作或 $2$ 操作序列仍然不降。那么 $1$ 操作直接线段树上二分然后打覆盖标记，$2$ 操作直接打标记即可。

考虑一般情况，发现某个时刻所有被 $1$ 操作影响过的 $i$（存在一次 $1$ 操作使得 $a_i \ge v$）组成的集合 $S$，$S$ 内部的序列是单调的。

于是整个序列被分成了两部分：$S$ 和 $[1, n] \setminus S$。对于 $S$，$1$ 操作直接线段树上二分然后打标记。$2$ 操作就分别对两个部分打个标记即可。

线段树一个结点需要维护：$S$ 部分的最大值及其最大下标（为了 $2$ 操作后计算新的最大值），两部分分别的和及其下标的和，$S$ 部分的元素个数和这个区间在 $S$ 部分的最大下标（打覆盖标记时需要将最大值的最大下标重置为这个值）。

剩下最后一个问题：如何计算一个元素何时加入 $S$。考虑二分 $mid$，相当于查询是否 $\exists j \in [1, mid], b_j \times i + a_i \ge v_j$（其中 $b_i$ 为第 $i$ 次 $1$ 操作前面的 $2$ 操作次数）。变形得 $\min\limits_{j = 1}^{mid} \{ -b_j \times i + v_j \} \le a_i$。考虑整体二分，维护一个 $(b_j, v_j)$ 的下凸包，check 就维护一个凸包上的指针即可。因为 $b_j$ 单调，所以不用排序。注意可能存在若干个 $b_j$ 相等，这种取它们 $v_j$ 的最小值即可。

总时间复杂度 $O(n \log n)$。

code