题解：P8987 [北大集训 2021] 简单数据结构

Purslane · 2025-07-26 22:47:21 · 题解

感觉这题还是比较套路的，放在当今 CNOI 大家肯定都能切穿了吧。

先考虑这样一个问题：如果 a 的初始值满足 a_1=a_2=\cdots = a_n = A 怎么办？

考虑将 \min 拆开（这种套路在涉及很多取 \min 的数据结构题中比较常见，举个例子就是 \min(a,\min(b,c)+d) = \min(a,b+d,c+d)，只有最外层一个 \min 方便使用数据结构维护）。

令 t 为当前操作 2 执行的次数，并且维护辅助数组 b。当执行了 1 操作（最开始我们可以认为 a_i = +\infty，并且执行了 v=A 的 1），对于所有的 b 执行 b_i \leftarrow \min\{b_i,v-it\}。

那么查询的时候 a_i=b_i+it，所以只需要维护 b 的区间和。

显然 b_i 是若干条 y=v-tx 的线构成的凸包。平衡树动态维护凸包肯定是可以的，但是发现斜率是递减的，所以维护一个栈就行。

所以为什么没有这个的部分分？？很奇怪啊。

回到原题，如果初始的时候假设 a_i=+\infty 那么上面的操作肯定还是对的，但是会算大了，因为每个 i 在最开始会有 b_i \leftarrow a_i。那咋办？

显然这个初始的 a_i 在某个时刻之后就没用了，可以直接套用上面那个做法。找到这个时刻 lim_i，在 lim_i 之前我们不需要考虑 1 操作，只是简单的区间加；在 lim_i 之后我们不用考虑初始值，可以用简单的区间赋值线段树维护。

那么，怎么找到这个 lim？

思路 1：我们对于每次操作 1，没有把原有的 a 覆盖掉需要初始的 a_i \le v- it。前 tmp 时刻都没更新，等价于这些限制都成立，所以我们要对于一大堆 (v,t) 求 v-it 的最小值。显然可以整体二分，这样是 O(n \log^2 n) 的。

思路 2：考虑直接上 KTT。容易势能分析得到复杂度为 O(n \log^2 n)。感觉不太好写，常数可能还不小。这样还不用离线，不好评价。

思路 3：在思路 1 中，为什么要用李超树呢？因为斜率是递减的，所以我们可以把凸包建出来，而建立凸包的过程只用到了栈，所以这一部分是 O(n \log n)；查询的时候也不用在凸包上二分，因为我们可以通过手段使得查询的横坐标是递增的，那么就可以使用双指针来做到线性。因此我们的整体二分在 O(n \log n) 完成。