题解 P7447

## 前言 好毒瘤啊好毒瘤啊好毒瘤啊好毒瘤啊 upd on 3.23:哈哈，原来最后一部分是 $\log n$ 分块，我还以为就是小常数暴力卡空间，学到了！ upd on 3.31:一处复杂度分析错误，感谢[水军带你飞](https://www.luogu.com.cn/user/50558)的指出。 ## 暴力 考虑暴力线段树。 * 区间 $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)$！ ## 总结 一道很好的倍增练手题（迫真）。