算法介绍
如果有一个序列上的多个区间询问，并且可以离线，且某区间 \([l, r]\) 推到 \([l + 1, r], [l, r + 1], [l - 1, r], [l, r - 1]\) 是比较容易的，那么可以使用一种较好的排序询问方式，使得总端点位移次数达到一个较小的值。
这种排序方式是：考虑对序列分块，对于两个区间，如果块不同，那么按块排序，否则按 \(r\) 排序。
考虑这个位移次数。对于 \(l\)，最坏情况是在块内左右横跳，\(S^2 \times \cfrac{n}{S}\) 的次数，并且这一部分常数小，跑不满。对于 \(r\)，每块内只会从左到右跑一次，\(\cfrac{n}{S} \times n\) 的次数。
将其平衡，那么 \(S\) 取 \(\sqrt n\) 可以达到理论的界 \(n \sqrt n\)。实际上由于常数可以将 \(S\) 调大一些。至于增加和删除操作所花费的时间，乘到总时间里即可。块长可以灵活调整，如果增删时间不同，也可以改块长。
有一个优化一倍常数的方式：对奇数标号的块，\(r\) 从小到大排序，否则从大到小排序。
实现上，通常先扩张区间然后缩小区间，也就是先进行 \(r++, l--\)。然后注意缩小区间的时候要先删除当前指针位置然后移动指针。
树上莫队
考虑树上括号序（进出的时候加入一次括号序）。对于询问：路径 \((s, t)\)，我们分两种情况将其转为括号序上的询问：
-
\(s\) 是 \(t\) 的祖先。那么 \(tail_t \rightarrow tail_s\)。
-
两者没有祖先关系，这代表两方括号序上区间不交，假设 \(s\) 在 \(t\) 前面。那么 \(tail_s \rightarrow head_t\)。
括号序内，出现两次的是不在路径上的子树，不做贡献。
如果询问的是点的相关信息，那么注意第二种情况并没有计算入 lca 的贡献。如果询问的是边的相关信息，考虑所有边都放到儿子的位置，这样做就是完全正确的了。
回滚莫队
对于并不支持删除操作的情况，可以这样做：
- 预处理每一个 \(l\) 到其块末尾 \(tail\) 的信息。
- 对于某一块内的询问，将 \(r\) 从小到大排序。对于块内的 \(r\) 暴力求解，对于块外的 \(r\) 维护 \([tail + 1,r]\) 的信息，然后和 \([l, tail]\) 合并。
分析时间复杂度：
- 预处理的时候，每一块从右往左每次需要复制和处理一个长度为 \(1, 2, ..., S\) 的块，总时间复杂度 \(O(nS)\)。
- 询问的时候，暴力的时间复杂度是 \(O(q_1S)\)。
- 其他的时间复杂度是 \(O(n\cfrac{n}{S})\)。
容易发现理论上最优复杂度依然是 \(O(n \sqrt n)\)。
对于“合并”的理解：有两种形式，一种是直接一个一个往左扫，这时候空间是很小的，不需要存块后缀信息，而复杂度是依然正确的，就是每次询问加了 \(O(\sqrt n)\)。还有一种就是保存后缀信息，并且合并。如果可以在 \(O(1) \sim O(\sqrt n)\) 的时间复杂度内完成合并，那么也是可以的，可能可以卡时间常数，但是空间复杂度变成了 \(O(n \sqrt n)\)（假设后缀信息的复杂度正比于其长度）。不过目前看好像大多数情况是第一种比较好。
同样，也可以是不支持插入的。（有的题就是删除更好做，用链表维护和 set 里插入的区别这样）。大概就是 \(r\) 从大到小排，然后某一块开始的时候取块首到 \(n\)，然后删两头这样。
标签：询问,sqrt,tail,排序,莫队,复杂度 From： https://www.cnblogs.com/Zeardoe/p/17235184.html