之前我并没有感觉到分块的暴力属性
今天卡常的时候莫名其妙的感觉到了
我甚至觉得自己经历了分块的诞生历程
今天本来在对一个分块题卡常
但是我直接写的纯暴力，一直差一点卡过
于是我想到了各种优化：
加 \(inline\) (别说还真有用)，加 \(register\) (感觉这个没用)...
\(bitset\) 记录之前这组询问有没有被访问过，有的话直接输出
事实上我还是没卡过
然后我就想到，如果我预处理出某一个区域，之后包含这个区域的询问不就可以优化了吗？
于是我预处理了中间的一块区域，经验证，预处理 \([\frac{n}{3},\frac{2n}{3}]\) 时取到最优复杂度 \(O(\frac{2n^2}{3})\)
可惜还是过不了，于是有了接下来的发现：
如果我预处理两个区域，不就能取得更优的时间复杂度了吗？
那如果三块，四块呢？
直到 \(\sqrt n\) 块，取得最优时间复杂度 \(n\sqrt n\) ，这便是分块了
标签：frac,暴力,分块,复杂度,sqrt,优雅,预处理 From： https://www.cnblogs.com/yhy-trh/p/chunking.html