莫队与分块

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。
  • $i<l$，$j < r$，$j > r$ 的情况同理。
• 一个小结论：若需要添加 （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$
• $1\leq n \leq 10^5$，保证答案在 int 范围内。
• • 若 $\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$ 的数的个数。
• $1\leq n \leq 10^5$，保证答案在 int 范围内。
• 对数列分块，设块长为 $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$ 的数的最大值。
• $1\leq n \leq 10^5$，保证答案在 int 范围内。
• 思路和上一题类似。
• 代码

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)$ 取模后的答案。
• $1\leq n \leq 10^5$，不保证答案在 int 范围内。
• 对数列分块，设块长为 $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$。
• $1\leq n \leq 10^5$，保证答案在 int 范围内。
• 将数列分块，设块长为 $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$ 取模后的结果
• $1\leq n \leq 10^5$，答案保证无需开 long long
• 对数列分块，块长为 $\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$ 次操作，操作分两种：
• $1.$ 查询区间 $[l , r]$ 第 $k$ 小值。
• $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$
• 代码