概述
将询问离线，按特定方式排序，使得询问之间移动的代价较小。
求所属块代码
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 循环内
1
2
3
4while(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--]];
普通莫队
-
记区间中有 $n$ 种颜色，颜色为 $i$ 的有 $a_i$ 个，则概率为
将询问离线，用莫队即可，时间复杂度 $O(n\sqrt{n})$。
带修莫队
-
将时间看作一维，即可变成三维问题 code。
分析时间复杂度，将一次操作看作一个点 $(t,x,y)$，将点按某一顺序排序，那么三个指针移动的总距离就是相邻点曼哈顿距离之和。分别考虑三个指针的移动即可，一般取块长为 $n^{\frac{2}{3}}$，时间复杂度为 $O(n^{\frac{5}{3}})$。
-
如果没有修改可以用只减不加的回滚莫队。此题 mex 是出现个数的，最大为 $\sqrt{n}$，所以每次移动完，直接暴力求解即可。code。
回滚莫队
-
一些题目删除操作并不好做，可以将其避免。
考虑计算复杂度的过程，每次 $l$ 指针的移动我们都是按 $\sqrt{n}$ 的次数计算。
这给了我们很大的操作空间：对于每次询问我们都可以将 $l$ 指针移动 $\sqrt{n}$ 次，而不改变时间复杂度。
每个块内右指针都是增加操作，左指针暴力计算即可。这样就只有增加操作了。
对于 $l$ 和 $r$ 在一个块内的，需要直接暴力计算。
树上莫队
将树拍扁转化为序列问题。一般可处理子树问题（dfs 序）、链问题（欧拉序）。
-
先求出欧拉序。对于 $(x,y)(dep[x]<dep[y])$ 路径，分讨一下
$lca = x$ 时，区间为 $[in_x,in_y]$。
$lca \ne x$ 时，区间为 $[out_x,in_y] \cup \{lca\}$。
出现两次的点不计入答案，可以用异或实现。
-
先求出 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]$ 为例，对某一颜色，它的贡献即为
左一预处理一下。左二是一维问题，排序求解。右一用莫队解。这样每个询问只需拆成 4 个查询，可过。
莫队二次离线
见某篇题解。
杂题
-
一个排列，一堆询问，求区间最长值域连续段，可离线。
对于区间询问，考虑莫队。将存在的数看作 $1$，查询即为最长的连续 $1$。每次需要将 $0$ 变 $1$ 和将 $1$ 变 $0$，或只需要其中一个并支持撤销。明显要用并查集，变 $0$ 为 $1$ 是好做的，撤销用可撤销并查集即可。按深度合并，答案为最大 $siz$，每次合并时记录一下即可。初始时每个点都为 $0$，可以记一个 $vis$ 记录每个节点是否为 $1$，当合并时特判一下。时间复杂度 $O(n\sqrt n\log n)$。
也可以观察最长连续 $1$ 性质。当加入 $x$ 时，更新 $x$ 点与当前段左右端点，因为中间不会再加数，不比 $x$ 点更优。
code。