普通莫队

莫队算法是一种离线算法，通常有多次询问，每次询问一区间。通过对询问进行排序，区间的伸长缩短来实现。

Code

注：初始化有一种更简单的方法：l = 1, r = 0;

可以证明块大小为 \(\sqrt n\) 时复杂度为 \(O(n \sqrt n)\)

设 \(B = \sqrt n\)，认为 \(n,m\) 同阶，那么当左端点在一个块内的时候右端点总共移动次数为 \(O(n)\)，故右端点移动次数为 \(O(n \sqrt n)\)；左端点几乎总是在块内移动，复杂度为 \(O(n \sqrt n)\)。故总复杂度为 \(O(n \sqrt n)\)。

例题

小B的询问

Tree and Queries （简单的拓展，搞一下dfs序，转化成序列问题即可）

小Z的袜子

带修莫队

支持修改的莫队。

加上一维时间轴。按照左端点所在块，右端点所在块，时间进行三关键字排序。

可以证明，块大小设为 \(n^{\frac{2}{3}}\) 时复杂度为 \(O(n^{\frac{5}{3}})\)。

具体来说，块大小为 \(n^{2/3}\) 时共有 \(n^{1/3}\) 个块，当左端点，右端点所在块相同时时间轴移动的复杂度总共为 \(O(n)\)，因此总复杂度为 \(O(n^{5/3})\)。左右端点每次移动的复杂度均为 \(O(n^{2/3})\)，故总复杂度为 \(O(n^{5/3})\)。

Code

树上莫队

参考资料：oi-wiki

仅学了括号序树上莫队。可以解决链上问题。

当DFS进入一个点时将其加入序列（左括号）；退出时再次加入序列（右括号)。得到的序列成为括号序。

对于一个直上直下的链 \(x...y\)，\(x = lca(x, y)\)，那么从 \(l(x)\) 到 \(l(y)\) 的异或和（出现第二次相当于删除）即为答案。

对于一个拐弯的链 \(x ... lca .. y\)，并且 \(r(x) < l(y)\)，那么从\(r(x)\) 到 \(l(y)\) 即为答案。手玩发现这里没有包含 \(lca\)，因为 \(lca\) 的俩括号把 \(x\) 和 \(y\) 完全括住了，最后加一下就好。

Code

题目

糖果公园：带修树上莫队