莫队与分块

JeffZhao · 2025-01-04 22:32:33 · 个人记录

P2709 小B的询问

给定一个长度为 n 的整数序列 a，值域 [1 , m]。有 q 个询问，每次给定一个区间 [l , r]，求 \displaystyle \sum_{i = l}^{r} c^{2}_i，c_i 表示数字 i 在 [l , r] 中的出现次数。
1 \leq n \leq 10^5$，$1\leq m \leq 10^5$，$1\leq k \leq 10^5
莫队模板题。
将原序列分成若干块，每块块长为 B，把所有询问离线下来，以左端点 l 所在块的编号 为第一关键字，右端点 r 的大小为第二关键字排序。
考虑维护指针 i 和 j 分别表示当前区间的左右端点，用 l 和 r 分别表示当前询问区间的左右端点
- 若有 i > l 则需要让 i 向左移动：i --，后删除 i cnt[a[i]] --，在删除的同时，更新一下当前的答案 ans。
一个小结论：若需要添加（add），则一定是先移动指针，后添加；若删除（del），则一定是先删除，后移动指针。
一个小细节：初始时，把 i = 1，j = 0，表示当前区间为空，还没有添加任何元素。
复杂度分析：
对于 i 的移动：
- 若两次询问的左端点 l 在一个块内，则两个询问之间最多需要 i 移动 B 次，q 个询问最多 q\times B 次
- 若两次询问左端点 l 所在的块变化，考虑分析最坏情况，画个图即可发现 i 移动距离不会超过 2\times n。因此复杂度忽略不计。
对于 j 移动：
- 若 j 移动时，两次询问的左端点 l 始终在一个块内，由于右端点 r 单调，每个块 内 j 移动次数总共不超过 n，\dfrac{n}{B} 个块，则 j 移动次数不超过 n\times \dfrac{n}{B} = \dfrac{n^2}{B}
- 若 j 移动时，两次询问的左端点 l 所在块发生了变化。\dfrac{n}{B} 个块，则最多发生 \dfrac{n}{B} 次这样的变化，每次 j 的变化最多是 n，则 j 的移动最多是 n \times \dfrac{n}{B} = \dfrac{n^2}{B}
由于 B 太大时，i 移动的复杂度过大；B 太小时，j 移动复杂度过大。考虑找到一个平衡点，令 \dfrac{n^2}{B} = q \times B，解得 B = \dfrac{n}{\sqrt{q}}。因此最终复杂度为 \mathcal{O}(n\times \sqrt{q})
trick：当块编号是奇数时，按照 r 递增排序；编号是偶数时，按照 r 递减排序。
代码

P1494 小 Z 的袜子

给定 n 个袜子，每一个袜子都有一个颜色 a_i
给定 q 组询问，每次给定一个区间 [l , r]，问从区间 [l , r] 随机抽出两只颜色相同袜子的概率。
1 \leq n \leq 10^5$, $1\leq q \leq 10^5$, $1\leq a_i \leq n
概率为 \frac{\displaystyle \sum_{i = 1}^{n} \binom{c_i}{2}}{\displaystyle \binom{r - l + 1}{2}}，c_i 表示颜色 i 在区间 [l , r] 出现的次数。
用莫队维护 c_i，以及 \displaystyle \sum_{i = 1}^{n} \binom{c_i}{2} 即可。
代码

P4462 [CQOI2018] 异或序列

给定一个长度为 n 的序列 a 和一个参数 m

有 q 组询问，每次给定两个参数 l , r，问有多少个点对 (i , j) 满足 l \leq i \leq j \leq r，并且 a_i \oplus a_{i + 1} \oplus ... \oplus a_j = m

1 \leq n \leq 10^5$，$1\leq q \leq 10^5$，$1\leq a_i \leq n

首先 a_i \sim a_j 的异或和可以用前缀异或和 S_i \oplus S_{j - 1} 来表示
莫队，考虑指针 i 和 j 移动时顺便更新答案。设 \text{cnt}[x][0] 表示 i \sim j 中 S_{k - 1} = x 的个数，\text{cnt}[x][1] 表示 i \sim j 中 S_k = x 的个数。
注意，移动指针时，\text{cnt}[x][0] 和 \text{cnt}[x][1] 都需要更新。并且 要注意更新 \text{cnt} 数组和更新答案的先后顺序！
代码

loj 6277

给定一个长度为 n 的序列 a。
n$ 个操作，每个操作都有三个参数 $\text{opt}$，$l$，$r$，$c
- 若 \text{opt = 0}，把区间 [l , r] 的每一个数都加上 c
- 若 \text{opt = 1}，查询 a_r 的值
对数列分块。build 时算出 p[i]，bl[i]，br[i]，分别表示 a_i 所在的块的编号，a_i 所在块的左端点的编号，以及右端点的编号。
修改时，先检查是否 l 和 r 在同一个块（即 p[l] = p[r]）。若在一个块，则暴力即可；若不在，给中间的整块打上加法标记，散块暴力即可。单次修改复杂度 \dfrac{n}{B} + B
查询时，直接让 a_r 和其所在块的加法标记相加即可。
令 \dfrac{n}{B} = B，得 B = \sqrt{n}，因此总复杂度 \mathcal{O}(m \sqrt{n})，m 表示询问次数
代码

loj 6278

给定一个长度为 n 的序列 a
n$ 个操作，每个操作都有四个参数 $\text{opt}$，$l$，$r$，$x
- 若 \text{opt} = 0，把区间 [l , r] 的数都加上 x
- 若 \text{opt} = 1，查询区间 [l , r] 小于 x 的数的个数。
对数列分块，设块长为 B。对每一个块维护一个递增的数列，以及区间的加法标记。
查询时，对于整块二分即可；对于散块直接暴力枚举即可。注意，由于区间有加法标记，所以要找的是这个块的递增数列第一个小于 x - \text{tag}[k] 的位置。\text{tag}[k] 表示 x 所在块的加法标记。单次查询复杂度 \frac{n}{B}\times \log B + B
修改时，对于整块，打上加法标记即可，并且维护的递增数列的单调性不会被破坏。对于散块，暴力给每个 a[i] 加上 x。由于破坏了散块递增数列的单调性，所以需要给这个块重新排序。单次修改复杂度 \frac{n}{B} + B\times \log B。
我们希望查询和修改复杂度能够相等，令 \frac{n}{B}\times \log B + B = \frac{n}{B} + B\times \log B，解得 B = \sqrt{n}，因此总复杂度 \mathcal{O}(n \times \sqrt{n} \times \log n)
代码

loj 6279

给定一个长度为 n 的序列 a
n$ 个操作，每个操作都有四个参数 $\text{opt}$，$l$，$r$，$x
- 若 \text{opt} = 0，把区间 [l , r] 的数都加上 x
- 若 \text{opt} = 1，查询区间 [l , r] 小于 x 的数的最大值。
思路和上一题类似。
代码

loj 6280

给定一个长度为 n 的序列 a
n$ 个操作，每个操作都有四个参数 $\text{opt}$，$l$，$r$，$x
- 若 \text{opt} = 0，把区间 [l , r] 的数都加上 x
- 若 \text{opt} = 1，输出 \displaystyle \sum_{i = l}^{r} a_i 对 (x + 1) 取模后的答案。
对数列分块，设块长为 B。对于每一个块，维护区间加法标记 \text{tag}[k] 以及区间和 sum[k]，\text{tag}[k] 表示这个块内的每个元素需要都加上 \text{tag}[k]，但现在还没有加。
修改时，对于整块，更新 tag[k] 以及 sum[k] 即可。对于散块，暴力更新 a[i] 和 sum[k] 即可，tag[k] 无需更新。单次修改复杂度 B + \dfrac{n}{B}
查询时，对于整块，直接查询 sum[k] 即可。对于散块，暴力累加 a[i] + tag[k] 即可。单次查询 B + \dfrac{n}{B}
令 B = \sqrt{n}，则单次查询和修改复杂度均为 \sqrt{n}，因此总复杂度 \mathcal{O}(m \sqrt{n})，m 表示操作次数。
代码

loj 6281

给定一个长度为 n 的序列 a
n$ 个操作，每个操作都有四个参数 $\text{opt}$，$l$，$r$，$x
- 若 \text{opt} = 0，对区间 [l , r] 中的每一个数 a_i 执行 a_i \leftarrow \lfloor \sqrt{a_i} \rfloor
- 若 \text{opt} = 1，输出 \displaystyle \sum_{i = l}^{r} a_i。
将数列分块，设块长为 B。维护块内区间最大值 mx[k]，以及块内区间和 sum[k]
修改时:
- 对于散块，暴力给 a_i 开根号，更新块内最大值即可，复杂度为 B。
- 对于整块，若块内区间最大值 mx[k] >1，则暴力给整个块的 a_i 开根号。枚举整块复杂度为 \dfrac{n}{B}。对于每一个整块，最多开 5 次根号，因此给整块暴力开根号的 总复杂度 为 \dfrac{n}{B} \times B \times 5 = 5\times n，可忽略不计。
- 因此，可以认为单次修改复杂度为 B + \dfrac{n}{B}
查询时，对于散块，暴力加 a_i 即可，复杂度 B。对于整块，直接加区间和 sum[k] 即可，复杂度 \dfrac{n}{B}。因此单次查询复杂度为 B + \dfrac{n}{B}
令 B = \sqrt{n}，则总复杂度为 \mathcal{O}(m\sqrt{n})，m 为操作次数
代码

loj 6282

给定一个长度为 n 的数列。
有 n 个操作，每次给定四个参数 \text{opt}，l，r，c
- 若 \text{opt} = 0，表示在第 l 个数字前插入数字 r
- 若 \text{opt} = 1，表示查询 a_r 的值。
根号重构
初始时，对数列分块，块长为 \sqrt{n}。
对于每一个块维护一个数组 b[k][x]，表示编号为 k 的块的数组的第 x 个元素，插入时，从小到大枚举块的编号，找到对应的块，插入即可。单次插入复杂度为 块的个数 + 对应的块的大小。
由于频繁的插入会导致某一个块的大小过大，最坏有可能是 n 级别的。因此每隔 \sqrt{n} 次插入，我们就重构一次，这样可以保证所有块的大小不超过 2\sqrt{n}。
插入复杂度为 \sqrt{n}，重构的总复杂度为 \dfrac{q}{\sqrt{n}} \times n= q\sqrt{n}
查询时，依旧从小到大枚举块的编号，找到对应的块即可。查询复杂度为 \sqrt{n}
总复杂度 \mathcal{O}(q \times \sqrt{n})
代码

牛客多校 Distance

给定一个 n \times m \times h 的空间。
有 q 次操作，每次给定四个参数 \text{opt}，x，y，z。
若 \text{opt} = 1，表示给点 (x , y , z) 打上标记
若 \text{opt} = 2，表示查询 (x , y , z) 到已经标记的点的曼哈顿距离的最小值。
1\leq n \times m \times h \leq 10^5$, $1\leq q \leq 10^5
根号重构。令 N = n \times m \times h
考虑暴力怎么做：把被标记的点塞到一个集合（vector）里面，每次查询的时候暴力枚举集合内的点。
但是我们不希望每次都枚举集合内所有点。
注意到不管关键点有多少个，把每一个关键点作为起点，跑一遍多源 bfs，都可以在 \mathcal{O}(N) 的时间复杂度内算出任意一个点到关键点的最小值。
考虑根号重构。每新标记 B 个点后就重新跑一遍多源 bfs，发现跑完 bfs 之后需要枚举的点不超过 B 个。因此复杂度为 \mathcal{O} (N\times \dfrac{q}{B} + q\times B)，令 B = \sqrt{N}，总复杂度为 \mathcal{O}(q\times \sqrt{N})
代码

loj 6283

给定一个长度为 n 的序列 a
n$ 个操作，每次操作给定四个参数 $\text{opt}$，$l$，$r$，$c
- 若 \text{opt} = 0，表示给 a_l \sim a_r 加上 c
- 若 \text{opt} = 1，表示给 a_l \sim a_r 乘上 c
- 若 \text{opt} = 2，表示输出 a_r 对 10007 取模后的结果
对数列分块，块长为 \sqrt{n}。对每一个块维护乘法标记 \text{tag}[k][0] 和加法标记 \text{tag}[k][1]
修改时，若是整块：
- 如果是区间加法，则直接让加法标记加上 c 即可
- 如果是区间乘法，则需要让乘法标记、加法标记都乘上 c
若是散块：一定要先下放标记（让散块内的每一个数都乘上 \text{tag}[k][0] 然后加上 \text{tag}[k][1]），然后再暴力修改。
代码

loj 6285

给定一个长度为 n 的序列 a
有 n 组询问，每次给定两个参数 l，r，表示询问区间最小众数。
1\leq n \leq 10^5$，$-2^{31} \leq a_i \leq 2^{31} - 1
对序列分块，块长为 \sqrt{n}。预处理 ans[i][j] 表示编号在 i \sim j 的块的最小众数，以及 cnt[i][j] 表示前 i 个整块内数字 j 出现的次数。预处理时，第一层枚举最左边块的编号 i，第二层枚举最右边的编号 j，第三层枚举第 j 块的所有数字，加入桶中，统计答案。复杂度 \mathcal{O} (n\sqrt{n})
查询时，先让答案（最小众数）继承整块的答案 ans[i][j]，然后枚举散块内的元素，加入桶中，某一个数 x 此时此刻出现次数为在整块出现次数 cnt[r][x] - cnt[l - 1][x]（l 和 r 分别是最左边整块和最右边整块的编号），加上在散块中出现次数 bucket[x]，尝试用二者之和更新答案即可。
代码

P2617 Dynamic Rankings

给定一个长度为 n 的序列 a

有 q 次操作，操作分两种：

2.$ 单点修改，把 $a_x = y

1\leq n,m \leq 10^5$，$0 \leq a_i,y\leq 10^9

算是动态二维数点吧，l \sim r 算第一维，第 k 小算第二维。
查询时，跳块即可。跳块复杂度 \mathcal{O}(\sqrt{n})，为了不让复杂度退化成 \mathcal{O}(n)，考虑根号平衡，设 w_{i , j} 表示值域在第 i 块，并且序列下标在 1 \sim j 块的个数，v_{i , j} 表示值域为 i，并且序列下标在 1\sim j 块的个数。这样就算出了 (值域上的整块，序列上的整块 ) 的个数，以及 ( 值域上的散块，序列上的整块 ) 的个数。
对于（值域上整块，序列上散块），可以先把序列上的散块的数 a_i 对应的值域上块的编号 \lfloor \dfrac{a_i}{B} \rfloor 装到桶里。对于（值域上散块，序列上散块）的个数，可以先把序列上的散块的数 a_i 加入桶里。
代码

牛客多校第 6 场 E Array

给定一个长度为 n 的序列，初始所有元素为 0

给定一个长度为 n 的序列 p，满足 1 \leq p_i \leq n，有 q 次操作吗，操作分两种：

1.$ 给定参数 $l$，$r$，$x$，给 $a_l \sim a_r$ 加上 $x

2.$ 给定参数 $l$，$r$，问 $\displaystyle \sum_{i = l}^{r} a_{p_i}

1\leq n \leq 10^5$，$1\leq x \leq 10^8

把问题放到二维平面上来看，(i , p_i) 表示第 i 列 p_i 行，查询相当于查 l \sim r 所有列的点权之和。修改相当于给 l \sim r 行所有点的点权加上 x
考虑把列分块，每 B 个分成一组。查询的时候可以查 整组之和 以及单独的列（即 a_{p_i}）
修改时可以直接考虑对 查询的整组 的贡献，对于每一组，把组内元素按照 p_i 排序，通过二分，可得有多少个组内元素的列 p_i 在 l \sim r 之内（记作 \text{cnt}），则本次修改对该组的贡献为 \text{cnt} \cdot x
修改时，对于零散的行，以及整块的行，考虑其对零散的列的贡献。其实，就是等价于：区间 +x，每次查 B 次某个具体的位置 a_{p_i} 的值。把行分块，根号平衡即可。
取 B = \sqrt{n \times \log n}，得到 \mathcal{O}(q \times \sqrt{n \times \log n} 的复杂度。代码
另一种做法是把所有点按照 p_i 排序，然后每 B 个分一组，这样，最多只有 B 个零散的点需要暴力修改。查询时，考虑对列分块，块长为 B
首先考虑修改对 查询时整块 的贡献。设 \text{cnt}(i , j) 表示第 i 组整体 +1 后对第 j 个整块列的贡献，h_i 表示第 i 组整体被加的标记。则查询时需要 枚举所有整组，需要 \mathcal{O}(1) 知道一个整组对一些整块的贡献，把 \text{cnt}(i , j) 的第二维前缀和即可。散点 +x 对整块的贡献设一个数组即可。
修改对 查询时散列 的贡献，可以和上个做法一样，用一个分块，也可以分别考虑修改时零散的点对查询时零散的列、以及整块的贡献。
注意 vector 的一些细节：对 ord 排序时，不能是单纯地 sort(ord.begin() , ord.end())，因为定义固定长度的 vector 时，初始里面的元素都是 0
代码