[Medium-Hard] P11733 [集训队互测 2015] 上帝之手

· · 题解

简要题意

注意这里的题意使用的字母相比于原题意的字母略有改动，本题解中以这里的字母为准。

给定两个长度为 n 的序列 d,l。若第 i-1 个时刻权值为 x_{i-1}，则 x_i\gets\min(x_{i-1}+d_i,l_i)。有 m 次操作，支持：

## 思路 DS trick 多合一，不可多得的练习题。 ### Part 1 先来考虑如何快速求出对于一个 $c$，从第 $c$ 个时刻开始，最终的 $x_R$。这并不困难，直接给出式子： $$ \min\left(x_{c-1}+\sum_{k=c}^{R} d_k, \min_{k=c+1}^{R+1}l_{k-1}+\sum_{i=k}^{R}d_i\right) $$ 大致就是要么没有受到上界的性质，要么枚举最后受到上界限制的点 $k-1$。由于所有可能情况都可以取到，我们每次更新 $x_i$ 只会选择最小的方案，所以需要取 $\min$。 于是预处理 $d$ 的前缀和，然后记一个 $F_k=l_{k-1}+\sum_{i=k}^{n}d_i$ 的 RMQ（由于带修改，所以需要动态化，可以用线段树之类的），就可以做到单次询问 $O(n\log n)$ 了。 ### Part 2 考虑如何快速做第一种询问。我们发现 $x_{c-1}\gets l_{c-1}$，所以对于每一个 $c$，结合 Part 1，$x_R$ 其实就是 $F$ 在区间 $[c,R+1]$ 的最小值减去 $d$ 的一个后缀和（这是常量）。 由于最小值单调不增，所以对于 $c<c'$，后者求出的 $x_R$ 更大。于是第 $k$ 大其实就是在 $c=R-k+1$ 处取到，于是转换为单点修改区间最大值问题，用普通的线段树即可解决。时间复杂度单次 $O(\log n)$。 ### Part 3 现在的任务是第二种询问，此时 $x_{c-1}$ 不再是 $l_{c-1}$，但是求第 $k$ 大改为了求最大值。这需要我们再次观察式子： $$ \min\left(x_{c-1}+\sum_{k=c}^{R} d_k, \min_{k=c+1}^{R+1}l_{k-1}+\sum_{i=k}^{R}d_i\right) $$ 观察到 $\min$ 的第一个参数，$f(c)=x_0+\sum_{k=c}^{R}d_k$ 关于 $c$ 不增，第二个参数 $g(c)=\min_{k=c+1}^{R+1} F_k-\Delta$（其中 $\Delta=\sum_{k=R+1}^{n}d_k$ 为常量）关于 $c$ 不降。 对于两个单调的且增减性不同的函数的最小值求最大值，一般用二分，找到它们的交点，则答案在交点取到（当然，如果没有整交点，则在交点两侧取到）。特别地，如果没有交点，则在某一个边界取到。 时间复杂度 $O(\log^2 n)$（一个 $\log$ 在二分，另一个 $\log$ 在求函数 $g(c)$ 的值）。 ### Part 4 最后需要解决的是第三种询问，我们需要求出种类数，$x_{c-1}\gets l_{c-1}$。由于 $x_{c-1}$ 与第一种询问相同，所以可以沿用处理第一种询问时得到的结论：对于每一个 $c$，$x_R$ 是 $F$ 在区间 $[c,R+1]$ 的最小值减去 $d$ 的一个后缀和。 于是我们需要单点修改 $F$ 上的一个位置，查询某一个区间的后缀最小值的种类数。参考 [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)，使用兔队线段树完成即可。具体可以参考[兔队的博客](https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html)。 时间复杂度单次 $O(\log^2 n)$。 故总时间复杂度 $O(n\log^\mu n+m\log^2 n)$ 可以通过本题（其中 $\mu$ 视实现可能为 $1$ 或 $2$）。 [Submission](https://uoj.ac/submission/739918)。