题解 P7447

dead_X · 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)！

总结

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