莫队学习笔记

莫队

莫队是一种常见的离线处理区间查询问的方法。

莫队的思想是把序列分块，然后把询问按照左端点所在块为第一关键字，右端点为第二关键字排序，然后处理询问，维护指针 \(l,r\) 表示当前处理的区间是 \([l,r]\)，每次根据询问区间来移动指针计算贡献。

关于复杂度。假设指针移动的复杂度是 \(O(p)\)，设块长为 B，那么就有 \(\dfrac{n}{B}\) 块。每个询问左端点最多移动 \(B\) 次，每一块的询问右端点最多移动 \(n\) 次，于是总移动次数就是 \(O(qB+\dfrac{n^2}{B})\)，当 \(B\) 取 \(\dfrac{n}{\sqrt{q}}\) 就可以做到 \(O(n\sqrt{q}p)\)。

关于常数，莫队的常数很小，而且可以用奇偶分块减小一半的常数。

P1972 [SDOI2009] HH的项链

题意：区间数颜色。

思路：把询问离线，然后跑莫队，用一个数组维护当前区间内每个数的出现次数，移动指针时，如果是加入一个数且这个数的出现次数是 0，就说明颜色数增加了 1；如果删除一个数且删除后出现次数为 0，那么颜色数就减少了 1。

「JOISC 2014 Day1」历史研究

题意：有序列 \(a\)，多次询问区间 \([l,r]\) 中 \(a_i\times cnt[a_i]\) 的最大值，其中 cnt 表示区间内出现次数。

思路：回滚莫队模板题。

首先考虑用莫队，但是我们发现在删除时不好维护最大值，那就想办法不删除，这就是回滚莫队。具体地，对于莫队指针的左右端点，右端点还是和普通莫队一样，每次往右移，然后记录下当前值。左端点就不太一样了，每处理完一次询问就回到左端点所在的段的末尾，然后令答案回到之前记录的值，这样就可以保证在不删除的情况下答案正确。

P4887 【模板】莫队二次离线（第十四分块(前体)）

题意：求区间中两个数异或值中有 \(k\) 个 1 的数对个数。

思路：莫队二次离线。

以前因为莫队二离是个很高端的东西，现在来看发现还好。

本质是把莫队端点移动时查询答案的操作再离线一遍，然后用一遍扫描线来计算。难点在于这样拆出来的询问有 \(O(n\sqrt{n})\) 的，需要进一步优化。

以右端点的移动为例，假设右端点从 \(r\) 到 \(r+k\)，那么我们要计算的就是 \(\sum\limits_{x=r+1}^{r+k}f(x,[l,x-1])\)，我们发现这个贡献是可差分的，于是就变成了 \(\sum\limits_{x=r+1}^{r+k}f(x,[1,x-1])-f(x,[1,l-1])\)，对于左边，这个值是可以预处理的，而后面就是 \([1,l-1]\) 对 \([r+1,r+k]\) 的贡献，可以用扫描线计算，这样我们就只有 \(O(n)\) 个询问了。

P3674 小清新人渣的本愿

题意：求区间是否可以选择两个数满足加和/差/乘积为 \(x\)。

思路：分开维护

对于“+”“-”，可以直接莫队维护区间值域 bitset。

对于“*”，可以直接枚举因数，再判断是否有 \(i,\frac{c}{i}\) 同时存在。

P4688 [Ynoi2016] 掉进兔子洞

题意：求 3 个区间的交的大小。

思路：做法还好，但是很难写。

首先，容易想到莫队 +bitset，但是这道题中同颜色可以有多个，不能直接用 bitset，要给每个颜色预留这个颜色大小的区域。

然后就是空间问题，需要把询问分3组来卡空间。

P4689 [Ynoi2016] 这是我自己的发明

题意：换根，求给出 \(x,y\)，从 \(x,y\) 的子树里各选一个点满足点权相等的方案数。

思路：首先，如果在 dfn 序上进行操作，那么每个点的子树就对应着1或2个区间。

记 \(f(l,r,L,R)\) 为第一个区间为 \([l,r]\)，第二个区间为 \([L,R]\) 的答案，这样状态是4维的，而这个信息显然是可以差分的，于是考虑怎么拆贡献。

考虑两种极端的情况，\(f(l,r,1,L-1)+f(l,r,R+1,n)\) 和 \(f(1,l-1,1,L-1)+f(1,l-1,R+1,n)+f(r+1,n,1,L-1)+f(r+1,r,R+1,n)\)，可以拆成 \(f(l,r,1,n)-f(l,r,L,R)\) 和 \(f(1,n,1,n)-f(l,r,1,n)-f(L,R,1,n)+f(l,r,L,R)\)，都转成了只有 \(f(l,r,L,R)\) 的情况，于是就好处理了。

转成差分后，就可以用莫队来求出每个区间的答案了。

P8078 [WC2022] 秃子酋长

题意：求区间排序后相邻的数在原序列中的位置的差的绝对值之和。

思路：终于来写秃子酋长了，上次看还是在WC的时候。

其实就是只删除莫队的板子。

考虑莫队，那么如果用常规莫队写法的话，加入一个点是 \(O(\log n)\) 的，那么就会让复杂度变为 \(O(n\sqrt{n}\log n)\)，考虑怎么优化。我们发现，如果我们预先处理好了每个数应该在什么位置，然后建链表，这样删除就只有 \(O(1)\) 了。

其实跟回滚莫队是差不多的。

P9340 [JOISC 2023 Day3] Tourism

题意：给出一颗 \(n\) 个节点的树，和一个长度为 \(m\) 的序列 \(a\)，\(q\) 次询问包含 \(a_{l\cdots r}\) 中所有节点的最小联通块大小。

思路：做了秃子酋长才发现这题好板。

用只删除莫队，然后按 \(dfn\) 序排序后建链表，再加上 \(O(1)LCA\) 就可以了。