省选-数据结构-莫队 · Zhl2010 第二博客

普通莫队

莫队就是优雅的暴力。

呃呃不想讲了，直接放代码：

C++

while(l<q[i].l)del(a[l++]);
while(l>q[i].l)add(a[--l]);
while(r<q[i].r)add(a[++r]);
while(r>q[i].r)del(a[r--]);

还有就是排序一般是按照块来的，又是还可以加上奇偶性优化：

C++

bool cmp(que a,que b){
	if(a.l/fq==b.l/fq)return ((a.l/fq)&1)?a.r<b.r:a.r>b.r;
	return a.l<b.l;
}

P3604 美好的每一天

P3604 美好的每一天。

对于只有 $26$ 个字母的题目，我们可以考虑状压。

我们可以发现，合法的区间需要保证字母出现次数为奇的最多有 $1$ 个。

由于这是子区间问题，我们考虑能不能前缀和。每一个 $s_i$ 表示每个字母出现的次数，然后子区间合法就是两个区间的数组异或起来，为 $1$ 的最多一位。

然后我们只需要加入点的时候寻找 $cnt[s_x]$ 或 $cnt[2^0,2^1,\cdots 2^k\oplus s_x]$ 。

带修莫队

相当于加上一个时间轴，就是现在已经修改到了多久了。

至于排序...我们判断如果 $l$ 和 $r$ 都在一个块里面，比较时间。

推荐块长 $n^{\frac{2}{3}}$ 。

回滚莫队

也叫不删除莫队。

我们发现，有的时候增加操作很好做，但是删除就不好了，所以我们需要一个不删除的莫队。

我们首先按照 $r$ 排序， $r$ 的移动一定不会向左，所以一定是增加操作，然后我们只需要考虑怎么移动 $l$ 了。

我们尝试分块，对于每一个块，都预处理出来这个块最右边的点到 $r$ 的这一段的答案，对于每一个 $l$ ，只需要每次从这个点转移，就是增加操作了。

复杂度每个询问均摊 $\sqrt n$ 的。

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

P5906 【模板】回滚莫队&不删除莫队。

这道题就直接用这个思路就行了，注意的是如果 $l$ 和 $r$ 在同一个块中，需要特判。

呃呃呃不调过样例，然后调了好久才过题。

其实还有一种写法，可能会更清晰一点，就是预处理出每一个块的节点，然后统一在一个函数内处理，这样会更清晰吧。

P8078 [WC2022] 秃子酋长

P8078 [WC2022] 秃子酋长。

我们需要知道我们做什么操作最快，如果是插入就是不删除莫队，如果是删除就是不加入莫队

思路

对于插入操作，我们只需要记录前驱后继就行了， $O(\log n)$ 的。

而对于删除，我们只需要链表就可以做到 $O(1)$ ，所以我们倾向于删除操作。

所以直接回滚莫队就可以做了。

P6349 [PA 2011] Kangaroos

P6349 [PA 2011] Kangaroos。

先考虑完全包含的大区间，因为这种情况往往会大区间的端点不在小区间中，不好判断。

然后后面就可以利用性质：只要区间端点在询问区间中两者就有交集。

问题转化成了值域上最长连续段问题，回滚莫队。

思路

首先，这道题我们需要在值域上进行莫队，然后维护连续合法区间。由于最长连续区间不支持删除，所以我们需要回滚莫队。

我们考虑具体需要怎么维护。需要注意的是，我们需要考虑完全包含的大区间，避免遗漏，因为这种情况往往会大区间的端点不在小区间中。然后后面就可以利用性质：只要区间端点在询问区间中，这个区间就需要加入答案。

回滚莫队中，我们先看整体都在块中的区间，这种情况很简单。我们设这个块在 $st\to ed$ 之间，先看包含的情况，就是这个区间 $l\le st$ 而且 $r\ge ed$ ，一定可以的，直接每次处理一个块的时候 $O(n)$ 预处理。还有就是计算开头在 $st\to ed$ 之间的区间，暴力枚举每个询问判断就行了， $O(q\times \sqrt n)$ 。

然后就是一般情况。这种情况一定可以的是一个端点在 $ed$ 左边，另一个在右边的区间。然后对于每个询问，进行 $r$ 的扩张，寻找以 $r$ 开头的合法区间。

至于写法...我们离散化的时候需要保证即使区间相同，最后离散化的值也不同（用 $id$ 就行了），这可以保证分块的均衡。

P5386 [Cnoi2019] 数字游戏

P5386 [Cnoi2019] 数字游戏。

普通的莫队做不了，我们在值域上进行莫队。

思路

大概思路就是我们在值域上莫队，然后将可行的值插入集合。

然后这个集合用分块维护，每个询问询问 $l,r$ 用分块查询即可。

思路是不是看上去很简单？但是代码是真的难写。

写法的话，我是每一个值域上的块用一个函数来计算。对于分块查询，建立一个 struct，维护各种操作。

P4074 [WC2013] 糖果公园

P4074 [WC2013] 糖果公园。

树上带修莫队。

之前做过，现在不想写了。。。

树分块

P6177 【模板】树分块 / Count on a tree II

P6177 【模板】树分块 / Count on a tree II。

普通树分块就是把树分成一块一块的。

比如我们需要查询两点之间的路径，我们可以类似数列分块，将块长为 $B$ 的放一组。然后我们通过分界点，一直向上跳跳到 LCA，这中间整块的部分分块解决，其余的散点暴力就行了。

也就是我们分块的时候，块内任意两点的距离都不超过 $B$ 。

没异或 lastans 过样例了。

还有双倍经验P3603 雪辉，数组开销 TLE。

还有 Top Cluster 树分块。

P9988 [Ynoi2079] 2stmo

P9988 [Ynoi2079] 2stmo。

树簇分块。将树划分为若干个树簇，满足每个树簇大小 $\le B$ 。

每个树簇内有两个界点，其他点为内点，满足两个树簇至多交于一个界点。

对于当前点 $u$ ，如果是以下情况，就会被标记成界点。

$u$ 子树内与 $u$ 在同一树簇内的界点数量超过 $1$ 。已有两个不同儿子的子树含关键点 -> 当前点必须成为关键点
$u$ 子树内与 $u$ 在同一树簇内的未被划分的边数 $\ge B$ 。
$u$ 是根节点。

回到这道题。我们发现这道题跟莫队还是很像的，问题可以转化成有一堆 $(u,v)$ ，移动代价是 $|sz_x-sz_u|+|sz_y-sz_v|$ 。

我们需要设计对这个“莫队”的排序，保证移动代价最小。

这时候，肯定会往分块去想，我们就需要用到树分块了。利用 Top Cluster 树分块的性质：所有块的大小不超过 $B$ 。

我们先分完块，将每个询问的节点放到界点上。这一部分复杂度 $O(qB)$ 。

然后对关键节点点对进行建树操作。我们考虑每个点可以向自己最大的儿子移动，这是最优的。自底向上遍历这棵树。

其实感性理解一下就行了，遍历整棵树的时间复杂度是 $O(n\sqrt n)$ 。

莫队二次离线

适用范围：

可以莫队。
更新答案的时间不是 $O(1)$ （一个数对答案的贡献与区间中别的数有关，例如比一个数小的数有多少）。

可以将 $O(nk\sqrt n)$ 的问题通过扫描线转化成 $O(nk+n\sqrt n)$ 的。

比如我们需要将 $[l,r]$ 变成 $[l,r+k]$ ，设 $x$ 对区间 $[l..r]$ 的贡献为 $f(x,[l,r])$ ，就转化成了：

$\sum _{x \in [r+1,r+k]}f(x,[l,x-1])$

可以进行差分。

$f(x,[l,x-1])=f(x,[1,x-1])-f(x,[1,l-1])$

我们发现 $f(x,[1,x-1])$ 可以预处理， $f(x,[1,l-1])$ 是动态的。

我们每一次将这些询问给存起来，最后一并计算 $f(x,[1,l-1])$ ，这就是进行第二次离线。每次询问的答案可以差分记录。

然后有 $O(n\sqrt n)$ 个点，会 MLE，我们需要优化。我们发现对于连续的移动， $x$ 不同，但是 $l$ 是相同的，所以我们只需要记录 $x$ 的左右端点就行了。

核心代码：

C++


		if(l>nl)v[r].push_back({nl,l-1,i});
		while(l>nl)del(f[--l]);
		if(r<nr)v[l-1].push_back({r+1,nr,-i});
		while(r<nr)add(f[++r]);
		if(r>nr)v[l-1].push_back({nr+1,r,i});
		while(r>nr)del(f[r--]);
		if(l<nl)v[r].push_back({l,nl-1,-i});
		while(l<nl)add(f[l++]);

注意这里面的 v 表示端点在那一段中，然后选取的前缀区间是 $v_x$ 。

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

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

利用性质 $a\oplus b=c\leftrightarrow b=a\oplus c$ 。

我们预处理出所有 $k$ 个 $1$ 的数，然后比较暴力地去做。

有一个很阴的地方就是 $k=0$ 的时候不能相同的数异或，答案需要 $-1$ 。

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II。

套模板就行了。

树状数组过不了，我们需要一个 $O(\sqrt n)$ 插入， $O(1)$ 查询的数据结构，我们想到了分块。

$sum_i$ 表示前 $i$ 块的和， $s_i$ 表示这一块前 $i$ 个数的和。

P8530 [Ynoi2003] 博丽灵梦

P8530 [Ynoi2003] 博丽灵梦。

二维带权数颜色。

莫队先维护一维，然后加入的另一维用分块。

先考虑一维的问题，有一个经典 trick：维护每个点的 $pre$ 表示上一个颜色与自己相同的数，查询 $[l,r]$ 就是找 $pre$ 在 $[0,l)$ 之间的数。