在线莫队

我竟然独立发现了这个东西...

考虑普通的莫队就是让区间加元素操作尽可能少，那么对于所谓的在线莫队，我们可以先跑出一些标准区间的值，然后在对他进行拓展，最终得出结果。

我们均匀的取出 \(B\) 个关键点，然后对于两两关键点算出答案。那么我们拓展区间时，最多要拓展 \(O(\frac{n^2}{B})\) 次，而预处理需要 \(O(nB)\) 时间，所以显然 \(B\) 取 \(\sqrt n\) 时最优，时间复杂度 \(O(n\sqrt{n})\)。

然而这样空间显然会爆炸。我的想法是可持久化，时空多一个 \(O(\sqrt{n\log n})\)，不过在网上搜索后发现如果原信息满足可减性，可以只维护 \([1,s_i]\) 的信息，空间多出一个 \(O(\sqrt{n})\)，而时间复杂度不变。