莫队

Idtwtei

2024-12-22

notes

概述

将询问离线，按特定方式排序，使得询问之间移动的代价较小。

求所属块代码

1	for(int i=1;i<=n;i++) bk[i]=(i-1)/LEN;

常见常数优化

左端点所在块相同时，按块编号的奇偶将右端点小到大或大到小排序

1	bool cmp0(Q a,Q b){ return bk[a.l]!=bk[b.l]?bk[a.l]<bk[b.l]:bk[a.l]&1?a.r<b.r:a.r>b.r; }

将简单的 add/del 写入 while 循环内

while(ql<dl) dans+=2*cnt[col[--dl]],cnt[col[dl]]++;
while(qr>dr) dans+=2*cnt[col[++dr]],cnt[col[dr]]++;
while(ql>dl) cnt[col[dl]]--,dans-=2*cnt[col[dl++]];
while(qr<dr) cnt[col[dr]]--,dans-=2*cnt[col[dr--]];

普通莫队

1.[国家集训队] 小 Z 的袜子

记区间中有 $n$ 种颜色，颜色为 $i$ 的有 $a_i$ 个，则概率为

$\frac{\sum_{i=1}^{n}a_i(a_i-1)}{(r-l+1)(r-l)}$

将询问离线，用莫队即可，时间复杂度 $O(n\sqrt{n})$

带修莫队

1.[国家集训队] 数颜色 / 维护队列

将时间看作一维，即可变成三维问题 code
。

分析时间复杂度，将一次操作看作一个点 $(t,x,y)$，将点按某一顺序排序，那么三个指针移动的总距离就是相邻点曼哈顿距离之和。分别考虑三个指针的移动即可，一般取块长为 $n^{\frac{2}{3}}$，时间复杂度为 $O(n^{\frac{3}{5}})$。

2.Machine Learning

如果没有修改可以用只减不加的回滚莫队。

此题 mex 是出现个数的，最大为 $\sqrt{n}$。

所以每次移动完，直接暴力求解即可。

code

回滚莫队

1.【模板】回滚莫队&不删除莫队

一些题目删除操作并不好做，可以将其避免。

考虑计算复杂度的过程，每次 $l$ 指针的移动我们都是按 $\sqrt{n}$ 的次数计算。

这给了我们很大的操作空间：对于每次询问我们都可以将 $l$ 指针移动 $\sqrt{n}$ 次，而不改变时间复杂度。

每个块内右指针都是增加操作，左指针暴力计算即可。这样就只有增加操作了。

对于 $l$ 和 $r$ 在一个块内的，需要直接暴力计算。

树上莫队

将树拍扁转化为序列问题。一般可处理子树问题（ dfs 序）、链问题（欧拉序）。

1.[WC2013] 糖果公园

先求出欧拉序。对于 $(x,y)(dep[x]<dep[y])$ 路径，分讨一下

$lca = x$ 时，区间为 $[in_x,in_y]$。
$lca \ne x$ 时，区间为 $[out_x,in_y] \cup \{lca\}$。

出现两次的点不计入答案，可以用异或实现。

2.[Ynoi2016] 这是我自己的发明

先求出 dfs 序，可以转化为区间查询（对于换根，分讨一下）。

差分一下，可以转化为双关键点问题，使用莫队求解。

但这样最多每次有 16 个查询

发现形如 $[1,x] \cup [y,n]$ 的询问可以拆为 $[1,n]-[x+1,y-1]$，有关 $[1,n]$ 的可以预处理一下

具体地，以 $[1,x] \cup [y,n] \times [1,x’] \cup [y’,n]$ 为例

对某一颜色，它的贡献即为

$(cnt_{[1,n]}-cnt_{[x+1,y-1]})*(cnt_{[1,n]}-cnt_{[x'+1,y'-1]}) \\ =cnt_{[1,n]} \times cnt_{[1,n]}-cnt_{[1,n]} \times (cnt_{[x+1,y-1]}+cnt_{[x'+1,y'-1]})+cnt_{[x+1,y-1]} \times cnt_{x'+1,y'-1}$

左一预处理一下。左二是一维问题，排序求解。右一用莫队解。

这样每个询问只需拆成 4 个查询，可过。