P8987 题解

EuphoricStar · 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