题解：P13977 数列分块入门 2·彻底怒了

FlowerAccepted · 2025-10-04 17:41:22 · 题解

0x-1 前言

保姆级分块板子教程。

这题我调了整整两天！（wssb?）

为了帮助广大 OIer 理解分块，为了防止我忘记自己的成果，为了给所有人避坑，也为了咕值， 本蒟蒻于刚通过本题之际，撰写此文。

希望大家能在本题解中寻得一些不一样的体验。

0x00 分块简介

分块是一种神奇的算法，号称「优雅的暴力」。思路是将数组分成若干个大块遵循「整块标记，散块暴力」的常规（具体接下来会解释）。

0x01 本题思路

0x00 基本建块

我们来看看一个长度为 11 的 \tt1-based 数组是如何分块的。我们首先设定块长 B=\lfloor\sqrt{n}\rfloor，于是有 \lceil\frac{n}{B}\rceil 个块。其中前 B 块是满的，有 B 个元素；剩下最多一个块（如果 n 是完全平方数则没有这个块）有 n - B^2 个元素。为什么取根 n 会在接下来解释。

有图有真相，看图更好理解：

[^1]

:::align{center} 图一
简单的建块例子「可鼠标悬停」 :::

与别的一些实现不同，我不想花费常数开销去存储一堆 L、R 等等数组。那么现在考虑怎么计算某个下标所在块的编号、起终下标与某个块的起终点。

首先看某个块 bx 的起终点 blkl(bx) 和 blkr(bx)。

观察图一可得块 bx 的终点 blkr(bx) 是 \min(bx\times B, n)。若它是完整的则为 bx\times B，否则按 bx\times B 算得的终点会超过 n，这显然是不对的，所以取到 \min。

又发现它的起点是「上一个块的终点（或零）」的下一项，所以有 blkl(bx) = (bx - 1)\times B + 1。

然后看某个下标 x 所在块的编号 id(x)。看图，注意到『「x 所在块的起点」的上一项下标』除以 B 刚好得到了「x 所在块的编号」减一的值，所以有 id(x) = \lfloor\frac{x - 1}{B}\rfloor + 1。

接下来的某个下标所在块的起终下标 cacl(x) 和 cacr(x)[^2] 就好办了，直接套上 blkl(id(x)) 和 blkr(id(x)) 即可。

这一部分代码：

int n, B; // 变量函数名如正文
inl_force int id(int x) { // 非递归函数强制内联优化效率
    return (x - 1) / B + 1;
}
inl_force int blkl(int bx) {
    return (bx - 1) * B + 1;
}
inl_force int blkr(int bx) {
    return min(bx * B, n);
}
inl_force int cacl(int x) {
    return blkl(id(x));
}
inl_force int cacr(int x) {
    return blkr(id(x));
}

0x01 进阶建块

我们已经完成了基本的建块，考虑如何完成题目的操作。

首先看到操作 \tt0：区间加。

那么我们想想，分了块，怎样才能优化加法？

肯定是把区间中的整块整体加，这里我们引入一个长度为块的数量的新数组：懒标记数组（lazy_{1\sim \lceil\frac{n}{B}\rceil}）。学过 \tt SgT[^3] 的童鞋们都知道这个东西。

转眼看操作 \tt1：查询 [l, r] 中小于 c^2 的数的数量。

既然是查询不等式，看来得二分，那么我们还需要维护序列每块内的有序版本。唔。

所以建块的时候同时要初始化排序后的数组，如下图（红色是 lazy，紫色是原数组，蓝色是排序后数组）：

:::align{center} 图二
进阶的建块例子 :::

这部分代码如下：

inl_force void rebuild(int bx) { // 重构（排序）块，因为后面还要用到所以定义函数
    for (int i = blkl(bx); i <= blkr(bx); i ++) { // 重新拷贝
        sorted[i] = a[i];
    }
    sort(sorted + blkl(bx), sorted + blkr(bx) + 1); // 加一是因为排序为左闭右开
}
inl_force void imp(int _n, Tp _a[]) { // 从数组导入块
    for (int i = 1; i <= _n; i ++) {
        a[i] = _a[i];
    }
    n = _n;
    B = sqrt(n); // 块长，记得 import cmath
    for (int i = 1; i <= id(n); i ++) { // 枚举的是块
        rebuild(i);
    }
}

现在，每一个数

那么具体怎么实现两个操作呢？

0x02 区间加

若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。

首先考虑 l，r 在一个块内的情况（如 4,5）。此时暴力枚举 [l, r] 并加 c（如 3）即可。结束后要重建整块。

:::align{center} 图三