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

感觉这题还是比较套路的，放在当今 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)$ 完成。