自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:09:50，当前版本为作者最后更新于2025-02-18 16:16:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

简要题意

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

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

• 0 p v 表示 $l_p\gets v$。
• 1 L R k 对于全体 $c\in[L,R]$，令 $x_{c-1}\gets l_{c-1}$，从第 $c$ 个时刻开始到第 $R$ 个时刻，求出最终的 $x_R$ 的第 $k$ 大值。
• 2 L R x0 对于全体 $c\in[L,R]$，令 $x_{c-1}\gets x_0$，从第 $c$ 个时刻开始到第 $R$ 个时刻，求出最终的 $x_R$ 的最大值。
• 3 L R 对于全体 $c\in[L,R]$，令 $x_{c-1}\gets l_{c-1}$，从第 $c$ 个时刻开始到第 $R$ 个时刻，求出最终 $x_R$ 的种类数。

$1\leq n\leq 10^5,1\leq m\leq 2\times 10^5,0\leq d_i\leq 10^4,0\leq l_i\leq 10^9$。

思路

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 楼房重建，使用兔队线段树完成即可。具体可以参考兔队的博客。

时间复杂度单次 $O(\log^2 n)$。

故总时间复杂度 $O(n\log^\mu n+m\log^2 n)$ 可以通过本题（其中 $\mu$ 视实现可能为 $1$ 或 $2$）。

Submission。