分块学习记录

Reference

link1
hzwer 分块9题

老年退役选手学点东西 之前学过分块但是已经忘得差不多了 今天稍微补一补吧。

用一道区间最值典题来讲一下。

\(1e5\) 数列 \([l,r]\) 最大值。

假设数组叫做 a 长度为 \(n\) 从一开始标号，那么就可以把这个数组分块 每一块的长度是 \(\sqrt{n}\) 这个长度是理论最优复杂度，我印象中看别人说使用不等式证明出来的。

然后是几个分块的典中典结论

\(a[i]处于(i-1)/sqrt(n)+1块\)

\(第i块的左端点为(i-1) \times sqrt(n)+1，右端点为min(i \times sqrt(n), n)\)

具体证明不知道 不过可以手模 个人觉得是很显然的。

接下来就是分块说烂了的一句话：大段维护，小段暴力。

具体来说就是提前预处理出每一块的最大值另外存起来 然后在查询时 对于整块的部分可以直接使用预处理最大值 对于不是整块的部分就 for 遍历查询。