NOI 一轮复习 IX：数据结构 B

本文是 NOI 一轮复习的终章，包括各类根号数据结构（以及其它数据结构杂项）。

在介绍一切内容之前，我们先介绍一种思想：平衡思想。

我们对于 $\ge B$ 和 $<B$ 的问题如果都有高效做法，那么可以考虑将它们拼起来，对于不同的部分使用不同的做法，从而得到一个求解整个问题的高效做法。

序列分块

分块是一种树形结构，可以视作一棵只有三层的树。

分类

动态分块可以支持修改，本质上是通过分块达到“大块维护，小块暴力”的方式来加速数据结构。

静态分块不支持修改，通过预处理一些信息来加速查询。本身功能是莫队的子集，但是其可以在线。

例题

一些题，有些比较复杂。

[Ynoi2019 模拟赛] Yuno loves sqrt technology III

Portal.

我们记录 $f(i,j)$ 代表第 $[i,j]$ 块的区间众数出现次数。我们对每一个数都开一个 STL vector，记录其出现的位置，并记 $ax[i]$ 为第 $i$ 个数出现在其 vector 中的位置。

整块的答案是可以直接统计的，而对于零散块，则获取当前的数在 vector 中的位置，考虑 $ans$ 是否可以变大，进行暴力更新即可。由于 $ans$ 最多变大 $2\sqrt{n}$，因此询问的时间复杂度为 $O(\sqrt{n})$。

总时间复杂度为 $O(n\sqrt{n})$。代码。

[Ynoi2019 模拟赛] Yuno loves sqrt technology I

Portal.

强制在线的区间逆序对！

• 整块内部：预处理；
• 散块内部：用树状数组预处理前后缀；
• 散块对散块：处理好每个数的排名，直接归并；
• 散块对整块：预处理出 $g_{i,j}$ 代表 $1\sim j$ 对 $i$ 块的贡献。

代码。

[CF453E] Little Pony and Lord Tirek

Portal.

预处理 $f_{i,k}$ 表示第 $i$ 块从全 $0$ 开始，$k$ 个单位时间后的和。由于区间推平操作的存在，颜色段均摊后复杂度是正确的。代码。

带插入区间 k 小

Portal.

设 $s_{i,j}$ 代表前 $i$ 个块落在第 $j$ 个值域块的数的个数，$v_{i,j}$ 代表 $i$ 块内值为 $j$ 的个数。然后所有信息都能够统计，块大的时候直接分裂即可。代码。

莫队

莫队，即高维扫描线，用一种合理的排序方式使得复杂度可以接受。

普通莫队

如果我们能够从得知对于当前区间，增加一个数和减少一个数对答案的增量，便可以直接莫队。

莫队可以卡常数。块的编号可以按照奇偶进行排序。

莫队可以支持修改，本质上就变成了三维扫描线。

复杂度分析

对于二维扫描线，设块长为 $B$，则时间复杂度为 $O\left(\cfrac{n^2}{B}+mB\right)$，前者是有 $n/B$ 个块，块的移动需要 $n$ 次，后者是每个询问需要 $B$ 次移动。发现 $B$ 取 $\cfrac{n}{\sqrt{m}}$ 可以做到 $O(n\sqrt{m})$ 的最优复杂度。

对于三维扫描线，时间复杂度为 $O\left(\cfrac{n^2 t}{B^2}+mB\right)$，因此可以取 $B=\cfrac{n^{\frac 2 3}t^{\frac 1 3}}{m^{\frac 1 3}}$。

树上莫队

对于查询链上的信息，有两种实现方式，一种是利用括号序将其拍到链上再做处理，另一种是正经的树分块做法。一般情况下采用前者足矣。

对于查询子树信息，此时不如直接树上启发式合并。

回滚莫队

莫队二次离线

正常莫队的话，我们可能需要 $O(\n\sqrt{m}\log n+m)$ 来完成区间逆序对（使用树状数组）。

将莫队的移动指针的求解过程视作 $n\sqrt{m}$ 次查询区间中满足特定特征的数的某个信息，如果这个信息可以差分，那么就成了对于前缀求解满足特定特征的数的某个信息。

考虑每次莫队区间改变时答案的改变。我们将更新的过程再次离线，来加速查询。设 $f(x,[l,r])$ 代表增加 $x$ 对于区间 $[l,r]$ 的贡献影响。那么差分掉，这样只需要挂 $O(2n\sqrt{m})$ 个询问！空间爆炸了！且由于空间爆炸导致时间爆炸！

观察贡献差分后的形式：$f(x,[1,x-1])-f(x,[1,l-1])$。发现贡献只有两类：

1. 减号左边的贡献永远是一个前缀和它后面一个数的贡献。这可以预处理出来。
2. 减号右边的贡献对于一次移动中所有的 $x$ 来说，$[1,l-1]$ 都是不变的。我们打标记的时候，可以只标记一个区间。

模板，所有的贡献都很方便计算，代码。

区间众数。同样采用二次离线莫队，这次需要对于 $L,R$ 的移动分别计算贡献。代码。

例题

一些题。

[Ynoi2015] 盼君勿忘

Portal.

考虑统计每个数 $x$ 出现 $y$ 次的贡献，其为 $x((2^{y}-1)\times 2^{len-y})=x(2^{len}-2^{len-y})$。对于出现次数相同的数一起统计，这样的数只有 $O(\sqrt{n})$ 个，链表维护即可。代码。

常见套路总结

根号分治（平衡）

考虑这样一个问题：

$O(1)$ 单点修改，$O(\sqrt{n})$ 查询区间和。

简单！分块维护块内的和，每次修改的时候更新块内和即可。

$O(\sqrt{n})$ 单点修改，$O(1)$ 查询区间和。

分块维护块内块外前缀和，也就是每个块内前 $x$ 个数的和和前 $x$ 块的和，那么查询就是 $O(1)$ 的了。

$O(1)$ 区间修改，$O(\sqrt{n})$ 查询单点。

将第一个差分掉直接做即可。

维护一个集合，$O(\sqrt{n})$ 插入数，$O(1)$ 查询 $k$ 小。

考虑值域分块，每个数维护其所在的块，对块维护一个有序表，插入的时候直接归并，$k$ 小就可以直接查询。

[IOI2009] Regions

Portal.

对集合大小进行根号分治，大集合预处理出答案，小集合可以对应到时间戳区间，先排序后再双指针扫描即可。代码。

[POI2015] ODW

Portal.

$k>B$ 的部分暴力跳，$k\le B$ 预处理即可。代码。

[CF840E] In a Trap

Portal.

式子中有一个树上距离不太好处理，我们考虑按照距离进行根号分治。

将每个点向上 $2^8$ 个点（包括自己）分为一块，这样向上跳的时候，每一块的后 $8$ 位不会产生影响。也就是说，我们预处理出 $g_{x,i}=\max_{j=0}^{255} a_{f_{x,j}}\oplus (256i+j)$ 代表 $x$ 所属的块内，$i$ 的值给定时的块内最大答案，其中 $f$ 表示 $x$ 的 $j$ 级父亲。

可以注意到加号前后两部分是互不影响的，那么将 $a$ 拆成前 $8$ 位和后 $8$ 位，前半部分将块内所有数值插入 01 Trie，然后查询前半部分的最大值 $ans$，后半部分直接开个桶，查询 $ans\oplus i$ 的最大值即可。

查询的时候直接从 $v$ 开始向上跳，整块直接获得答案，散块暴力即可。

时间复杂度 $O(n\sqrt{n}\log n+q\sqrt{n})$。代码。

[CF1056H] Detect Robots

Portal.

就是要判断是否出现过 $x\rightarrow a\rightarrow \cdots\rightarrow y,x\rightarrow b\rightarrow \cdots\rightarrow y$ 的情况。

根号分治。对于小串，对于每个终点 $y$ 开一个 vector，push_back 所有的起点对应的 $(x,t)$ 对，总个数是 $O(n\sqrt{n})$ 的。对于大串，记录所有点的出现位置，对于每个串从后往前扫，记录当前最大的终点位置然后判断即可。代码。

数据结构杂项

以下内容可能不太常用，但是因为某些原因我们选择将其记录在这里。随缘填坑。

根号重构

即所谓的“操作分块”：在根号次操作后重构数据结构来计算影响。

[APIO2019] 桥梁。

操作分块。块之前的修改直接处理掉，块内部的按照重量限制排序然后枚举所有询问，不需要修改的边按照重量限制依次添加，再枚举需要修改的边按照时间进行修改，然后直接可撤销并查集维护这一阶段的修改，对于一个块内这一步是 $O(m\log m + m +B^2)$ 的。代码。

树分块

倍增值域分块

即通过 $[B^i,B^{i+1})$ 的方式进行分块，在特定问题上有着特定的用途。

[Ynoi2007] rgxsxrs

Portal.

暴力做法是直接势能线段树，但很遗憾，势能是 $O(nV)$ 的。

我们可以考虑将数按照大小分为几组，这样只需要每次对每组进行均摊。按照值域倍增就很对，跳出当前值域块的数就下方到下一个值域块，每个数最多跌落 $\log_B V$ 次，时间复杂度为 $O(B m\log n\log_B V)$。

由于卡空间，所以需要底层分块。

代码。

题车

其实没什么东西了。

刷基础

一些基础题。

[CF1406E] Deleting Numbers

Portal.

考虑求出 $x$ 的质因数幂次。

对 $\sqrt{n}$ 以内的质数可以暴力搞。然后剩下的都是大质数，最多只会出现一次。如果直接扫过去需要 $2m$ 次询问（$m$ 为质数个数），那么将 $B$ 个质数分为一块，一块一块地去检查，就只需要 $m+2\sqrt{m}$ 次询问。代码。

[Ynoi2014] 不归之人与望眼欲穿的人们

Portal.

分块维护每个块的前后缀信息和块内答案，然后询问直接用大双指针扫。只会保留 $O(\log a)$ 个有效前缀和后缀，最后时间复杂度 $O(n\sqrt{n}\log a)$。代码。

刷提升 1

全面应用数据结构！

[Ynoi2018] 未来日记

Portal.

使用带插入 $k$ 小的方式来维护 $k$ 小值，用并查集维护将一个数改为另一个数，整块改值，散块直接重构。

注意要跳过无效修改，这个卡常很有效。代码。

[Ynoi2018] 五彩斑斓的世界

Portal.

离线，逐块处理。我们需要一个可以在 $O(m)$ 完成单个块内处理的算法。

记块内最大值为 $k$，那么：

• $k\le 2x$，令大于 $x$ 的数减去 $x$ 后就没有比 $x$ 大的数了，$k$ 会减小至少 $k-x$；
• $k>2x$，令小于等于 $x$ 的数加上 $x$，就没有比 $x$ 小的数了。然后打上全局减标记，$k$ 在操作后减少至少 $x$。

发现这个 $k$ 单调不增，那么时间复杂度为 $O(V)$。

维护数值时直接采用并查集，记录集合的大小。零散块修改直接重构，整块则直接维护。代码。

刷提升 2

进一步提升数据结构能力！！

[Ynoi2007] tmpq

Portal.

暴力 DP 可以将 $i,k$ 的贡献拆开然后暴力扫然后乘起来即可。

看上去就非常的离谱，以前给出的做法大概是这样的：

直接操作分块，每次只有 $O(\sqrt{m})$ 个被修改的数，然后就有看每个数是否是在这个块内被修改的，$8$ 种情况都能做，就是有点无语。

有一种聪明的做法，转化为 $a,b,c$ 单点修改，$b_i=a_j=c_k$ 的个数。先写一个动态 DP 维护转移。

对于每个出现的 $w$ 的次数进行根号分治。对于 $cnt_w\le B$，那么进行暴力 DP，然后差分贡献，扔到相应的位置上，询问相当于求前缀和，$O(n\sqrt{n})$ 次修改，$O(m)$ 次查询，使用 $O(1)-O(\sqrt{n})$ 的分块维护。

对于 $cnt_w>B$，离线扫一遍操作序列，单点修改前缀查询，由于修改的总个数是 $O(m)$，询问个数是 $O(m\sqrt n)$，因此使用 $O(\sqrt{n})-O(1)$ 的分块维护即可。代码。

[集训队互测 2018] 完美的队列

Portal.

只需要求出每一个颜色什么时候死了的就行了，分整块和散块统计贡献。

整块直接计算需要加多少次整个块的 push 才能被爆掉，如果块内有散 push 直接重构。

散块直接扫描线，然后数据结构上二分出这个颜色能撑到什么时候。代码。