自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:29:57，当前版本为作者最后更新于2021-03-22 09:44:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

好毒瘤啊好毒瘤啊好毒瘤啊好毒瘤啊

upd on 3.23:哈哈，原来最后一部分是 $\log n$ 分块，我还以为就是小常数暴力卡空间，学到了！

upd on 3.31:一处复杂度分析错误，感谢水军带你飞的指出。

暴力

考虑暴力线段树。

• 区间 $a_i$ 最大值 $\leq x$，此时修改已经失去意义。
• 覆盖修改区间，$a_i$ 最小值 $>x$，此时打标记退出。

时间复杂度 $O(m\min(\log_2n,a_i))$，由于数据水可以拿很多分。

思路

考虑按照值域倍增分块，进制为 $b$。

也就是说，$[b^i,b^{i+1})$ 会被分在一个块里，于是我们得到了 $\log_ba_i$ 块。

我们把每个数再额外求出一个 $s_i$ 表示它距离这一块最小值的距离。

对于每一块建立线段树。

修改时，我们在每一棵线段树上暴力，仍然在以下几种情况返回：

• 区间 $a_i$ 最大值 $\leq x$，此时修改已经失去意义。
• 覆盖修改区间，$s_i$ 最小值 $\geq x$，此时打标记退出。
• 到达叶子节点，发现 $s_i<x$，重构这个节点，退出。

然后查询的时候就直接推标记返回真实值就好了。

这样的复杂度是多少的呢？

注意到我们在一棵线段树上修改的时候，如果 $s_i$ 的最小值都 $\geq x$，复杂度是 $\log_2n$ 的，因此总复杂度是 $O(m\log_ba_i\log_2n)$ 的。

但是可能会有 $s_i<x$ 需要被重构的节点把单次修改的复杂度搞的很大，这部分可以均摊分析一下。每个 $s_i<x$ 必定会至少向下跌落 $1$ 块，因此一个 $a_i$ 最多只能向下跌落 $\log_ba_i$ 块，一次跌落只会占用 $\log_2n$ 的复杂度，均摊下来是 $O(n\log_ba_i\log_2n)$ 的。

还有一个问题是 $a_i\leq x$ 的部分，即和 $x$ 同块的线段树上的复杂度。这部分事实上就等同于只分 $1$ 块的暴力，由于每个数最多只能被减 $b\log_ba_i$ 次，时间复杂度为 $O(mb\log_2n\log_ba_i))$。

因此这题的时间复杂度是 $O((n+m)\log_ba_i\log_2n+mb\log_2n\log_ba_i)$，空间复杂度是 $O(n\log_ba_i)$。

不难发现 $b$ 取一个接近 $e$ 的数（比如 $2$ 或者 $4$）就是最优的，但是被毒瘤出题人卡了空间。

于是我们可以将整个序列按 $\log_ba_i$ 大小分块，块间线段树，块内暴力，这样线段树每次查询和修改只会暴力修改 $O(1)$ 个块，在时间复杂度并没有提升的情况下空间复杂度直接变成了 $O(n)$！

总结

一道很好的倍增练手题（迫真）。