概述

平方分割又叫做分桶法或者分块法，把排成一排的 $N$ 个元素每 $√N$ 分在一个块（桶）里，这样的分割方法可以把对区间的操作的复杂度降至 $O(√N)$。

对序列平方分割

一般的做法是预设一个整数 $S$（$S$=$⌈√N⌉$），将序列分成 $B$（$B$=$⌈NS⌉$）块，每块 $S$ 个元素。对于一个区间的操作分为块内操作和块间操作，块内的暴力求解，块间的高效求解（排序后二分，lazy标记，预处理，数据结构维护等）。

1
2
3
4
5
6
//定义块号和块边界
for (int i=0; i<n; ++i) {
    belong[i] = i / S;
    L[i] = belong[i]*S;
    R[i] = min(n, L[i]+S)
}
1
2
3
4
5
6
7
8
9
10
//区间询问或区间修改
for (int i=l; i<=r; ) {
    if (i == L[i] && R[i] < r) {
        //need efficient algorithm
        i = R[i];
    } else {
        //just use brute force
        i++;
    }
}

题目

POJ 2104 K-th Number

题意
有 $n$ 个数字，$m$ 次询问，询问$[l,r]$区间里第 $k$ 大的数字。
题解
这题是主席树的经典题目，在本文中尝试用分块的方法求解。
对元素的位置分块，每块分别排好序，二分第 $k$ 大的数字 $v$ ，对于一个区间 $[l,r]$ 查询小于 $v$ 的个数分为块内查询和块间查询，块内元素一个一个判断是否小于 $v$ ；块间用二分查找来统计小于 $v$ 的个数。
二分复杂度：$O(logN)$，单次查询复杂度：$O(S+BlogS)$
总时间复杂度：$O(M(logN(S+BlogS)))$
code

UVA 12003 Array Transformer

题意
有一个数组 $A[1,…,n]$ 和 $m$ 条指令和一个数字 $u$ ，每条指令形如 $(l,r,v,p)$ ，统计出 $A[l],A[l+1],…,A[r]$ 中严格小于 $v$ 的元素的个数为 $k$ ，然后把 $A[p]$ 改为$\frac {uk}{r-l+1}$。问变换后的最终数组。

题解

对元素的位置分块，每块分别排序。询问的操作同POJ 2104，修改的操作则在 $p$ 所在的块里进行，因为修改后块内元素基本有序，所以用 插入排序 的方法使得被修改的元素移动到正确的位置。单次修改的复杂度： $O(logS+S)$ ，单次查询的复杂度：$O(S+BlogS)$ 总时间复杂度：$O(M(S+BlogS))$ 类题：SPOJ RACETIME Race Against Timecode

拓展
若本题修改不是单点修改，而是区间修改，那么也没有必要重新全部排序：

本来数组是有序的，现在把其中一部分加上了一个数，那么可以将原数组分为修改后的和没修改的两部分，每部分都是一个有序数组，可以在 $O(S)$ 的时间内 归并排序。 ——《非常规大小分块算法初探》 徐明宽

BZOJ 2957 楼房重建

题意
一个人在坐标 $(0,0)$ 看楼房，楼房定义为 $(xi,yi)$ 表示位置在 $x_i$ ，高度为 $y_i$ 。如果这栋楼房上任何一个高度大于0的点与 $(0,0)$ 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。起初所有楼房的高度都为0，有 $M$ 次操作，每次修改某个楼房的高度，问每次操作结束后能从 $(0,0)$ 看到多少栋楼房。
题解
如果一栋楼房可见，那么最高点 $(xi,yi)$ 和 $(0,0)$ 在x轴上的斜率一定大于前面所有的楼房，也就是要求斜率单调递增的序列的长度。
对楼房的位置分块，每个块维护斜率递增的序列。修改操作直接在某个块上重新计算斜率递增的序列（可以使用插入排序算法），查询操作在每个块里二分查找大于前一个块里的最大斜率的斜率，并更新当前最大斜率。
单次修改复杂度：$O(S)$，单次查询复杂度：$O(BlogS)$
总时间复杂度：$O(M(BlogS+S))$
code

HDOJ 4366 Successor

题意
有 $n$ 个人，编号为0的是老板，编号1到 $n−1$ 是员工，每个员工只有一个上司，除老板为每个人有他的忠诚值和能力值。每次要解雇一个人的时候，从他的下属中选取能力值大于他的且忠诚值最高的一个，若不存在则输出-1。共 $m$ 次询问，每次询问解雇编号为 $i$ 的员工会选择哪个编号的员工顶替他。（所有询问都不相互影响）
题解
显然是一棵树，用DFS序得到编号的序列，每个点能知道子树在序列上对应的区间。对序列分块，每块的元素按照能力值排序，简单的dp求得能力值更大的后缀里忠诚值的最大值。块内查询逐个遍历，块间查询二分查找大于解雇员工的能力值的位置，从而得到最大的忠诚值，又因为忠诚值互不相同，所以能用map对应到员工的编号。
单次查询复杂度：$O(BlogS)$
总时间复杂度：$O(M(BlogS))$
code

BZOJ 2002 Bounce 弹飞绵羊

题意
有 $n$ 个弹力装置，每个装置有一个弹力系数$ k_i$ ，如果绵羊到达第 $i$ 个装置，它会被弹到第 $i+k_i$ 个装置。有 $m$ 个操作，修改某个装置的弹力系数，或者询问从某个装置出发弹几次后会被弹飞。
题解
对装置的位置分块，预处理出每个块维护从块里每个位置出发要弹几次后弹出该块，以及弹出后到达的位置。修改操作直接在某个块上重新计算要维护的信息，查询操作利用每个块的信息可以 $O(1)$ 跳出该块，累计次数和即可。
单次修改复杂度：$O(S)$，单次查询复杂度：$O(B)$
总时间复杂度：$O(M(S+B))$
code
拓展
本题的加强版：CodeForces 13E Holes
增加单点修改的操作以及询问最后被弹飞的位置。
做法类似，预处理中增加从块里每个位置出发最后弹出该块的位置
code

CodeForces 551E GukiZ and GukiZiana

题意
有 $n$ 个数字，$m$ 次操作：1. $[l,r]$ 区间里的所有数字都增加 $x$ ；2. 询问 $[1,n]$ 里的最远点对 $(i,j)$ 满足 $a_i=a_j=y$ 。
题解
类似线段树的区间修改，对每一个块添加lazy标记表示该块统一增加的总和。每块分别把 $pair(a[i],i)$排好序，若块内元素被修改则重新排序，询问时只要对所有的块二分 $(y−lazy[b])$ 求出最近左端点和最远右端点即可。
单次修改复杂度：$O(SlogS+B)$，单次查询复杂度：$O(BlogS)$
总时间复杂度：$O(M(SlogS+BlogS))$
code

CodeForces 444C DZY Loves Colors

题意
有 $n$ 个数字，第 $i$ 个数字$a[i]=i$ ，有 $m$ 次操作：1. 修改 $[l,r]$ 区间的数字为 $x$ ，设原来的值为 $y$ ，那么该位置改变量累加 $|x−y|$；2. 询问 $[l,r]$ 区间的改变量的总和。
题解
对每一个块设置lazy标记表示该块的相同的值（如果不相同则标记为0），$sum[i]$ 表示第i个数字非lazy修改（即直接单点修改）的改变量和，$sumlazy[b]$ 表示第 $b$ 块里每一个数字经lazy修改的改变量和，$sumblock[b]$ 表示第 $b$ 块经lazy修改的所有数字的改变量总和。每次区间修改最多出现两个没有lazy标记的块，所以需要暴力单点更新的块不会很多。块内询问每个数字的贡献值总和：$∑(sum[i]+sumlazy[b])$；块间询问每个块的贡献值总和：$∑sumblock[b]$。
单次修改复杂度：$O(S+B)$，单次查询复杂度：$O(S+B)$
总时间复杂度：$O(M(S+B))$
code

CodeChef QCHEF Chef and Problems

题意
有 $N$ 个数字，第 $i$ 个数字 $A[i]≤M$ ，$K$ 次询问：问在 $[L,R]$ 中相同数字的位置的最大间隔。
题解
由于没有修改操作，可以预处理一些信息来辅助求解。
对序列分块之后进行预处理：
块间预处理：$ans[i][j]$ 表示第 $i$ 块到第 $j$ 块区间里的最大间隔，通过prepre数组记录每个数字最早出现的位置实现。然后就可以 $O(1)$ 得到块间最大值。
块内预处理：$pos0[b][v]$ 表示第 $b$ 块里 $v$ 最后出现的位置，然后转为前 $b$ 块的最后出现的位置；同理可得 $pos1[b][v]$ 表示第 $b$ 块之后 $v$ 最早出现的位置。然后暴力求解即可，求解方法和块间预处理相同。
块间预处理复杂度：$O(BN)$，块内预处理复杂度：$O(N+BM)$
总时间复杂度：$O(BN+BM+KS)$
code
类题：SPOJ ZQUERY Zero Query（提示：求前缀和）

LYOI 147 「分块」区间众数

题意
给一个长度为 $n$ 的序列，$m$ 次询问，每次查询一个区间 $[l,r]$ 内的众数（如果有多个众数，取最小的一个），强制在线。
题解
同样没有修改操作，类似上题预处理一些信息。
对序列离散化，分块之后进行预处理：
块间预处理：$ans[i][j]$ 表示第 $i$ 块到第 $j$ 块区间的众数，通过 $cnt$ 数组记录每个数字出现次数实现。然后就可以 $O(1)$ 得到块间最大值。
块内预处理：$sum[b][v]$ 表示第 $b$ 块里 $v$ 出现的次数，然后转为前 $b$ 块的出现的次数。然后暴力求解即可，求解方法和块间预处理相同。
块间预处理复杂度：$O(BN)$，块内预处理复杂度：$O(N+BN)$
总时间复杂度：$O(BN+S)$
code
拓展
带修改操作：区间众数解题报告 - 陈立杰

CodeForces 455D Serega and Fun

题意
有 $n$ 个数字，$q$ 次操作，1. 序列循环向右移动一位；2. 询问 $[l,r]$ 里 $k$ 的个数。强制在线。
题解
使用块状链表解决：
用deque或者list存储每块的元素，移位操作在每块 $O(1)$ 地插入或删除。
预处理出每块中每个元素的个数，移位时也可以 $O(1)$ 修改。
总时间复杂度：$O(Q(B+S))$
code

HDU 4391 Paint The Wall

题意
有 $n$ 个数字，$q$ 次操作，1. 将 $[l,r]$ 里的所有元素涂成颜色 $z$；2. 询问 $[l,r]$ 里 颜色 $z$ 的个数。
题解
颜色范围很大，如果使用朴素的线段树空间上无法承受。
线段树套分块哈希：考虑线段树维护的不是单个元素，而是整块元素，每块用 map 维护每种颜色的数量，再加上懒惰标记后可以通过此题。
总时间复杂度：$O(Q(B+SlogS)$
code

对集合平方分割

通常在图中使用，具体做法是预设一个整数$S$（$S$=$√E$），将度数超过 $S$ 的点记为重点，其余的点记为轻点。重新建图：重点只与相邻的重点连边，重点与相邻的轻点的边的信息使用预处理或者数据结构等手段高效维护，使得对点的遍历和边的修改的复杂度降至 $O(√E)$ 。

题目

HDU 4858 项目管理

题意
有 $n$ 个点，$m$ 条边的无向无环图，两个节点可能有多条边，每条点有权值，有 $q$ 次操作，1. 节点 $u$ 的权值加上 $v$；2. 问节点 $u$ 相邻点的权值和。
题解
根据重点和轻点的定义，将原图重新建图，若 $u$ 是重点，$sum[u]$ 保存与 $u$ 相邻的 重点 的权值和。修改 重点 的话更新该点和与该点相邻的 重点 的 $sum$（单次修改复杂度：$O(S)$；单次查询复杂度：$O(1)$），否则在原图遍历所有相邻点的 $sum$（单次修改复杂度：$O(S)$；单次查询复杂度：$O(S)$）。
总时间复杂度：$O(QS)$
code

HDU 4467 Graph

题意
有 $n$ 个点，$m$ 条边的无向无环图，每条边有权值 $w$，每个点有颜色 $(0/1)$，有 $q$ 次操作，1. 第 $x$ 个点的颜色反转；2. 问端点的颜色是 $(A,B)$ 的边的权值和。（$A(B)=0/1$）
题解
根据重点和轻点的定义，将原图重新建图，预处理若干信息，若 $u$ 是 重点，$sum[u][0/1]$ 保存与 $u$ 相邻的 重点（轻）点 的边权和，$ans[k]$ ($k=0$: 0-0; $k=1$: 0-1; $k=2$: 1-1) 保存统一类型的边权总和，修改只要交换信息即可，查询能 $O(1)$ 得到答案。
code

ZOJ 3749 Chameleon

题意
有 $n$ 个集合，第 $i$ 个集合有 $m_i$ 个数字，所有数字都不相同，$q$ 次操作，每次选取第 $i$ 个集合和第 $j$ 个集合，按照数字大小归并排序，问排序后相邻数字之间所属集合不同的个数。
题解
按照朴素的方法，复杂度是 $O(QN)$ 。按照集合的大小以 $S=√N$ 分类，两个集合都小于 $S$ 的询问按照朴素的方法解决，复杂度为 $O(QS)$ ；如果大于 $S$ ，考虑离线询问，对于一个大于 $S$ 的集合，$O(N)$ 处理出其他所有集合和它的答案，那么复杂度为 $O(NS)$。总时间复杂度：$O((N+Q)S)$
code

CodeForces 348C Subset Sums

题意
有 $n$ 个元素，第 $i$ 个元素的值为 $a[i]$ ；有 $m$ 个集合，每个集合存有若干个元素的下标（一个元素可能在多个集合出现）。$q$ 次操作，1. 询问某个集合元素值的总和；2. 第 $k$ 个集合内所有元素的值加上 $x$。
题解
按照集合的大小以 $S=√N$ 分类，预处理大于 $S$ 的集合内元素值的总和以及大集合之间重合的元素的个数，修改时用lazy标记记录；查询根据lazy标记集合之间重合元素个数转移来求得。对于小于 $S$ 的集合的操作暴力计算或者和上述做法类似。总时间复杂度：$O(QS)$
code

CodeForces 398D Instant Messanger

题意
作为一个聊天房间的管理员，需要支持用户登录，退出，添加朋友，删除朋友，统计在线朋友的数量这四种操作。
题解
对用户的朋友数量动态分割，不再按照某一个固定的值来分隔。对于比当前用户朋友数少的用户用数组维护个数，比当前多的用户遍历统计。
code

CodeForces 576C Points on Plane

题意
给出 $n$ 个点，要求排序后，相邻两点的曼哈顿距离之和小于等于 $2.5×10^9$。
题解
按照 $x$ 坐标每1000长度分块，块内按照 $y$ 坐标排序，那么可以构造出距离上限是 $2×10^9$ 的方案，满足题意。
code

对询问平方分割

莫队算法用到了分块的思想，一般是给 $Q$ 个区间 $[l,r]$ 来进行的一些操作和询问。
将序列分成 $√N$ 块，每块的大小为 $√N$ 。离线处理 $Q$ 个区间：首先对左端点 $l$ 所在的块号从小到大排序，如果块号相同则按右端点 $r$ 从小到大排序。然后用双指针移动到当前区间位置，每次移动更新对结果的贡献。

1
2
3
4
5
6
7
for (int i=1; i<=Q; ++i) {
    while (L < q[i].l) sub(L++);  //删除
    while (L > q[i].l) add(--L);  //增加
    while (R < q[i].r) add(++R);
    while (R > q[i].r) sub(R--);
    ans[q[i].id] = sum;  //答案
}

CF 86D Powerful array

CodeForces 351D Jeff and Removing Periods 莫队
HDU 4638 Group 莫队
CodeForces 103D Time to Raid Cowavans 莫队
CodeForces 375D Tree and Queries 莫队
CodeForces 617E XOR and Favorite Number 莫队
SPOJ DQUERY D-query 莫队
CodeChef GERALD07 Chef and Graph Queries 莫队，并查集，LCT
CodeChef IITI15 Sherlock and Inversions 莫队，区间逆序对