题解：P13976 数列分块入门 1

lcfollower · 2025-09-06 20:43:17 · 题解

修改

闲话

:::info[无关内容] 哎这题是数列分块 1 的板子为啥黄？哦原来是可以用 BIT 做。但是好像评难度的跟不上时代，BIT 板子已经绿了。

我以前数列分块都是在团队里交的，数据范围也和原题一样，然后我那个团给数列分块 9 题都评了红，我们底下就流传了切红题等于切数列分块。

后来知道了 loj 就交了几道到 loj 上。

然后盼了好久，终于等到了这一天——洛谷竟然也上传数列分块入门系列 9 题了（终于没有红了）！

:::

前置知识

• 暴力。

• 线段树的懒标记思想。

• 会基础的时间复杂度分析。

引入

序列分块是什么？

它是一种算法，可以把它当作优雅的暴力。

对于这道题，我们对于操作 0 有个朴素的暴力：

for(int i = l ; i <= r ; i ++) a[i] += c;

这样操作 1 就可以直接输出 a_r，最坏时间复杂度为 \mathcal O(Qn)，其中 Q 为操作次数，在本题中就是 n，下文还是会突出 Q 而非 n。

那么我们能不能把 \mathcal O(n) 的修改给减少一点时间呢？

现在我们可以把序列抽相成若干个长度为 1 的块，每次 a[i] += c 都是在修改一个块的元素。

那么我们能不能把序列重新抽象成由若干个长度为 B 的块组成，这样一次暴力的时间复杂度是否能减少呢？

抽象过后的序列

举个例子，比如 a = [1 ,4 ,2 ,3 ,5 ,3]，此时取 B = 3，那么就可以抽象为 a = [[1 ,4 ,2] ,[3 ,5 ,3]]，取 B = 4 可以抽象为 a = [[1 ,4 ,2 ,3] ,[5 ,3]]（注意这里最后一块长度不满但是没什么大关系）。

操作 0

我们先抛开预处理，直接来看操作怎么解决。

现在我们有个长度为 10 的序列 a = [1 ,1 ,4 ,5 ,1 ,4 ,1 ,9 ,1 ,9]，现在取 B = 3。

相同颜色的框内的数均在同一个块中。

现在我们要将 a_{[2\dots 8]} 加上 5。

我们发现，修改的区间有一些块是完整的修改块，又有一些块是只修改一部分的修改块。我们把完整的修改块称为整块，修改一部分的块成为零散块。容易发现零散块最多只有 2 个，分别位于修改区间的左和右端点。因此我们把左边的零散块称为左零散块，同理右边的为右零散块。

比如上图的整块为蓝块，左零散块为红块，右零散块为粉块。

此时，我们发现整块可以直接 \mathcal O(1) 修改。具体地，就是和线段树一样的懒标记，把这个块的懒标记增加 5。

我们记 belong_i 为节点 i 所属的块，这个在下面的建块里可以预处理。为了方便代码书写，如果修改区间不存在整块，我们也把最左边和最后边的整块当作零散块。

//[x ,y] 为修改区间，val 为该修改操作增加的值。
//tag[i] 为块 i 的加法懒标记。
#define up(i, x, y) for(int i = x ; i <= y ; i ++)
up(i, belong[x] + 1, belong[y] - 1) tag[i] += /*5*/ val;
//由于最左、最右块我们都看作了零散块，因此最左和最右的两个块的懒标记不能修改，因此 belong[x] + 1 <= i <= belong[y] - 1。

容易计算得整个序列有 \lceil \frac{n}{B}\rceil 个块，那么对于修改整块，最多修改 \max\{0 ,\lceil\frac{n}{B}\rceil - 2\} 个整块，一次修改时间复杂度为 \mathcal O(1)，因此时间复杂度为 \mathcal O(\frac{n}{B})。

现在还有左右两个零散块没有更新过，此时我们不能打上标记，那怎么修改呢？

我们想到一种很暴力的做法：直接暴力给每个值增加 5。

现在我们记 l_i 为块 i 的左端点编号，r_i 为块 i 的右端点编号，这个我们可以在下面的建块预处理得到。

那么左边零散块需要暴力修改的位置为 [x ,r_{belong_x}]，右零散块需要暴力修改的位置为 [l_{belong_y} ,y]。

//很板的暴力。
up(i, x, r[belong[x]]) a[i] += val;
up(i, l[belong[y]], y) a[i] += val;

明显，一次循环最多修改 B 个值，那么两个循环最多修改 2B 个值，时间复杂度为 \mathcal O(B)，那么操作的 0 时间复杂度就为了 \mathcal O(B + \frac{n}{B})。

现在还有一个特殊情况，如果修改区间内，没有任何整块呢？

既然零散块不能直接打标记（标记是给整块打的），那么能不能直接暴力呢？

因为一个块的长度最长为 B，我们可以暴力修改，时间复杂度为 \mathcal O(B)，这样做当且仅当 belong_x = belong_y。

if(belong[x] == belong[y]) {
  up(i, x, y) a[i] += val;//暴力做。
  return ; //要么回溯写 return，要么不写下面写 else。
} /*else*/

提一嘴给加法打懒标记的正确性很显然，做过线段树 1 的应该显然。

操作 1

这个是单点查询，我们直接输出 a_r + tag_{belong_r} 即可，即一开始的序列值，暴力修改的序列值，以及懒标记的值的和，前两个就是 a_r，后面的为 tag_{belong_r}。

那么如果是区间查询呢？

和区间修改一样的，我们需要额外维护一个 sum_i 表示块 i 的总和，这个只对于原序列，预处理完就不更改了。

那么查询时：

• 整块的和：sum_i + tag_i \times (r_i - l_i + 1)。

• 零散块的和：暴力累加 a_i 就好。

修改还是一模一样。

建块

好了，这两个操作都要把块建出来才行。

我们首先计算块的数量 num = \lceil \frac{n}{B}\rceil = \lfloor\frac{n - 1}{B}\rfloor + 1 = \lceil \frac{n + B - 1}{B}\rceil，下取整 C++ 里是有个整除的所以尽量用下取整，它方便。

然后对于块 i（1\le i\le num），我们能得到 r_i = i\times len，这个显然有 i 个长度为 len 的块那么右端点就是 i\times len。然后可以计算得到 l_i = (i - 1) \times len + 1 = r_{i - 1} + 1，即块 i 的左端点为块 i - 1 的右端点右边一个位置。

注意可能 r_{num} > n，因为最后一个块的长度可能不满 B，因此循环完写上 r[num] = n 即可。

然后对于下标 i 所属块的编号 belong_i（1\le i\le n），显然的就是 \lceil \frac{i}{B}\rceil，同样地，转化为下取整计算即可。

len = B /*待定*/ ,num = (n - 1) / len + 1;
//len 即为 B，num 为块的数量。 
up(i, 1, num){
    l[i] = (i - 1) * len + 1;
    r[i] = i * len;
//计算块的左右端点。
}
r[num] = n;//不要忘了。

up(i, 1, n) belong[i] = (i - 1) / len + 1; //计算 i 所属的块的编号。

建块的时间复杂度为 \mathcal O(\frac{n}{B} + n)，显然最坏情况下为 \mathcal O(n)，下文就不讨论这个时间复杂度了。

当然可能有的麻烦点的建块时间复杂度为 \mathcal O(nB)，比如序列分块入门 9。