综合

分块算法学习笔记

$$\huge \rm 分块$$

$$\Large 算法分析$$

$\quad$考虑一些在序列上的区间操作，如区间加和区间求和。

$\quad$直接暴力做单次操作复杂度是 $\Theta(n)$，总时间复杂度 $\Theta(qn)$.

$\quad$如果将序列分成 $\sqrt{n}$ 块，每块长度为 $\sqrt{n}$，并且对每个块维护里面所有元素的和，即可在 $\Theta(\sqrt{n})$ 的复杂度内进行单次操作。

$\quad$具体实现如下：

• 令块的数量为 $num=\sqrt{n}$，单个块的长度为 $siz=\lceil\frac{n}{num}\rceil$.

• 记 $bel_i$ 表示 $i$ 号节点属于第几个块。

• 可以记录一些题目需要用到的信息，如 $sum_i$ 表示第 $i$ 个块内所有元素的和。

$$\Large \rm 数列分块入门九题$$

$\large \rm T1-区间修改，单点查询$

$\quad$对每个块维护整块加的值，查询的时候加上即可。

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$\large \rm T2-区间修改，查区间内小于某个数的个数$

$\quad$对每个块内的元素排序，区间修改时整块大小顺序不变，散块暴力排序，查询时二分即可。

$\quad$时间复杂度 $\Theta(n\sqrt{n}\log n).$

$\quad$排序使用归并可以将复杂度优化到 $\Theta(n\sqrt{n\log n}).$

$\large \rm T3-区间修改，区间查前驱$

$\quad$同样是排序后在块内二分，只不过是把求比他小的数的数量改成求比它小的数中最大的那个。

$\quad$时间复杂度 $\Theta(n\sqrt{n}\log n).$

$\quad$排序使用归并可以将复杂度优化到 $\Theta(n\sqrt{n\log n}).$

$\large \rm T4-区间修改，区间求和$

$\quad$维护每个块的和以及加的数，用类似 $\rm T1$ 的方法维护。

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$\large \rm T5-区间开方，区间求和$

$\quad$我们发现开方操作是没办法全局维护的，于是考虑寻找开方操作的性质。

$\quad$我们发现每个数被开方几次以后就会变成 $1$（或者它本身就是 $0$，但这部分显然没有贡献，可以直接删去），于是对每个块记录一下里面 $1$ 的个数，如果全都是 $1$，就不对它进行开方，否暴力开方即可。

$\quad$求区间和还是维护一下每个块的和。

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$\large\rm T6-单点插入，单点查询$

$\quad$我们发现暴力做的时候需要将所有数向后移一位，单次时间复杂度 $\Theta(n).$

$\quad$于是考虑分块，给每个块预留 $\sqrt{n}$ 的剩余空间用来后移，记一下当前块的长度即可。查询的时候每访问一个块就把查询编号减去当前块的长度。不难发现这样做单次操作时间复杂度 $\Theta(\sqrt{n}).$

$\quad$但是我们发现一个问题，如果插入全在一个块内的话复杂度很快就会变成 $\Theta(n)$，于是考虑每进行插入操作 $\sqrt{n}$ 次就重构分块即可。

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$\large\rm T7-区间修改（包含加和乘），单点查询$

$\quad$考虑对每个块记 $\rm add$ 和 $\rm mul$，表示块内元素的真实值为 $a\times \rm mul+add$，区间加的时候，给 $\rm add$ 加上 $k$ 即可，区间乘的时候，不仅需要给 $\rm mul$ 乘上 $k$，还需要给 $\rm add$ 乘上 $k.$

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$\large\rm T8-区间查询数的个数并全部修改成这个数$

$\quad$我们发现如果询问区间小的话查询和修改都很容易，如果询问区间大的话会把很长一段都变成相同的数。如果记录一个块是否都是同一个数的话就很容易维护了。

$\quad$不难发现这样做复杂度是 $\Theta(n\sqrt{n})$ 的。

$\large\rm T9-询问区间最小众数$

$\quad$记 $s_{i,j}$ 表示前 $i$ 个块中 $j$ 出现的次数，$p_{i,j}$ 表示第 $i$ 个块到第 $j$ 个块的众数。

$\quad$我们发现，对于一次询问，答案一定是整块的众数或散块的众数，这个只需要对比一下即可。

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$$\Large\rm 习题$$

$\large \rm [TJOI2009]开关$

$\quad$记 $c_i$ 表示第 $i$ 盏灯是否开着，$sum_i$ 表示第 $i$ 个块中有多少盏灯开着，$d_i$ 表示第 $i$ 个块的状态是否整体改变。

$\quad$对于区间取反操作，零散操作直接修改 $c_i$，并根据 $c_i$ 和 $d_i$ 决定 $sum_i+1$ 或 $-1$. 整块操作不用改变 $c$，直接令 $sum_i=R_i-L_i+1-sum_i$，并且将 $d_i$ 取反。

$\quad$对于区间求和操作，零散点求和直接加上 $c_i\oplus d_i$，整块求和则加上 $sum_i$.

$\quad$单次操作复杂度 $\Theta(\sqrt{n})$，总时间复杂度 $\Theta(q\sqrt{n})$.

$\large \rm [LG3396]哈希冲突$

$\quad$转化题意，设计一种数据结构，支持：

• 单点修改

• 求从某一点 $pos(pos\leqslant d)$ 开始，以步长 $d$ 遍历数列，求所经过的所有数之和。

$\quad$考虑根号分治。

$\quad$对于 $d\geqslant \sqrt{n}$ 的询问，直接暴力查询。

$\quad$对于 $d \leqslant \sqrt{n}$ 的询问，记 $sum_{i,j}$ 表示从 $i(i\leqslant \sqrt{n})$ 开始，步长为 $j(j\leqslant \sqrt{n})$ 的答案。预处理的时候直接枚举计算即可，时间复杂度 $\Theta(n\sqrt{n})$.

$\quad$对于修改操作 $a[pos]\leftarrow x$，先直接在原数列上进行修改，再考虑其对 $sum$ 数组造成了什么影响。易知，对于步长为 $d$ 的预处理数组，只会对 $sum_{pos\%d,d}$ 造成影响，于是对每个 $d(d\leqslant \sqrt{n})$ 修改一下即可，单次修改时间复杂度 $\Theta(\sqrt{n})$.

$\quad$总时间复杂度 $\Theta[(n+q)\sqrt{n}]$.

$\large \rm [LG2801]教主的魔法$

$\quad$考虑分块。

$\quad$记原数列为 $A$，将 $A$ 复制一份记为 $B$，将 $B$ 分块，块内排序。

$\quad$对于修改操作，整块直接打标记，散点修改完后再块内排序，这样完成操作后仍能保持分块数列的性质，单次操作复杂度 $\Theta(\sqrt{n}\log\sqrt{n})$.

$\quad$对于查询操作，二分查找第 $i$ 个块内有多少个元素不小于 $k-add_i$，单次操作复杂度 $\Theta(\sqrt{n}\log \sqrt{n})$.

$\quad$总时间复杂度 $\Theta[(n+q\sqrt{n})\log n]$.

$\quad$考虑再对复杂度做一些优化，令块的大小为 $s$，则修改操作若采用归并排序，单次操作复杂度为 $\Theta(s+\frac{n}{s})$，同时单次查询复杂度为 $\Theta(s+\frac{n}{s}\log s)$. 当询问次数为 $q$ 时，总复杂度为 $\Theta[q(s+\frac{n}{s}\log n)]\geqslant \Theta(q\sqrt{n\log n})$，取最小值当且仅当 $s=\sqrt{n\log n}$.

$\large \rm [国家集训队]排队$

$\quad$分块 $+$ 树状数组。

$\quad$考虑交换两个数 $a_u$ 和 $a_v$ 的贡献：

• 显然 $u$ 左边的数和 $v$ 右边的数没有贡献。

• 对于 $a_u$ 来说，贡献为 $u$ 到 $v$ 之间比它大的数的数量减去比它小的数的数量。

• 对于 $a_v$ 来说，贡献为 $u$ 到 $v$ 之间比它小的数的数量减去比它大的数的数量。

$\quad$至于如何计算 $u$ 到 $v$ 之间比某个数大或小的值的数量，分块后散块直接暴力，整块建两颗树状数组即可。

$\quad$令块大小为 $siz$，则时间复杂度为 $\Theta[nlogn+q(siz+\frac{n}{siz}logn)]\geqslant nlogn+q\sqrt{nlogn}$，取最小值当且仅当 $siz=\sqrt{nlogn}$，此时块的数量 $num=\sqrt{\frac{n}{logn}}$.

$\large \rm [LG4168]Violet蒲公英$

$\quad$考虑分块，记 $s_{i,j}$ 表示前 $i$ 个块中颜色为 $j$ 的数量，$p_{i,j}$ 表示第 $i$ 个块到第 $j$ 个块的众数。

$\quad$对于一次询问，先求出整块中的众数、众数的出现次数和所有在零散块中出现了的颜色的数量。显然，如果零散块中出现的颜色没有一个比众数出现的次数多，那么要求的众数就是整块的众数，否则是出现次数最多的颜色。

$\quad$时间复杂度 $\Theta(n\sqrt{m})$. 此时块大小 $B=\frac{n}{\sqrt{m}}$.