莫队算法

· · 个人记录

普通莫队

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

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

题目

糖果公园：带修树上莫队

回滚莫队

有些时候扩展的复杂度是 O(1) 的，但是收缩的复杂度可能达到 O(n)，我们需要一种只需扩展的莫队。

仍然类似普通莫队那样排序（l 所在块为第一关键字，r 为第二关键字），对于每个 “l 所在块”我们一次性处理：首先把 nwl 指针放到那个块的右边，nwr 指针放到那个块的右端点。对于每个询问，我们先移动 nwr 指针，这个是不用撤销的；然后移动 nwl 指针，这个是得到答案以后要撤销的。

如果发现 l,r 在同一块内，暴力解决。

可能需要用到可撤销数据结构。注意撤销时要撤销完所有需要撤销的东西。

详见oi-wiki

代码：

int nwl = 0, nwr = 0, lst = 0;
for (int i = 1; i <= m; ++i) {
    int l = qy[i].l, r = qy[i].r, id = qy[i].id;
    if (blong[l] != lst) {
        ...
        res = stop = 0;
        nwl = ed[blong[l]] + 1; nwr = ed[blong[l]];
        lst = blong[l];//bug
    }
    if (blong[r] == blong[l]) ans[id] = jzpforce::sol(l, r);
    else {
        while (nwr < r) ++nwr, ins(a[nwr], nwr);
        int memor = res, memop = stop;
        while (nwl > l) --nwl, ins(a[nwl], nwl);
        ans[id] = res;
        res = memor;
        nwl = ed[blong[l]] + 1;
        while (stop > memop)    cancl(stk[stop--]);
    }
}