专栏文章

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

FFlowerAccepted
P13977题解参与者 11已保存评论 15

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
15 条
当前快照
1 份
快照标识符
@minpcbn4
此快照首次捕获于
2025/12/02 06:09
3 个月前
此快照最后确认于
2025/12/02 06:09
3 个月前
查看原文

0x-1 前言

保姆级分块板子教程。
这题我调了整整两天！（wssb?）
为了帮助广大 OIer 理解分块，为了防止我忘记自己的成果，为了给所有人避坑，也为了咕值， 本蒟蒻于刚通过本题之际，撰写此文。
希望大家能在本题解中寻得一些不一样的体验。

0x00 分块简介

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

0x01 本题思路

0x00 基本建块

我们来看看一个长度为 1111 的 1−based\tt1-based 数组是如何分块的。我们首先设定块长 B=⌊n⌋B=\lfloor\sqrt{n}\rfloor，于是有 ⌈nB⌉\lceil\frac{n}{B}\rceil 个块。其中前 BB 块是满的，有 BB 个元素；剩下最多一个块（如果 nn 是完全平方数则没有这个块）有 n−B2n - B^2 个元素。为什么取根 nn 会在接下来解释。
有图有真相，看图更好理解：
1
图一
简单的建块例子「可鼠标悬停」
与别的一些实现不同，我不想花费常数开销去存储一堆 LL、RR 等等数组。那么现在考虑怎么计算某个下标所在块的编号、起终下标与某个块的起终点。
首先看某个块 bxbx 的起终点 blkl(bx)blkl(bx) 和 blkr(bx)blkr(bx)。
观察图一可得块 bxbx 的终点 blkr(bx)blkr(bx) 是 min⁡(bx×B,n)\min(bx\times B, n)。若它是完整的则为 bx×Bbx\times B，否则按 bx×Bbx\times B 算得的终点会超过 nn，这显然是不对的，所以取到 min⁡\min。
又发现它的起点是「上一个块的终点（或零）」的下一项，所以有 blkl(bx)=(bx−1)×B+1blkl(bx) = (bx - 1)\times B + 1。
然后看某个下标 xx 所在块的编号 id(x)id(x)。看图，注意到『「xx 所在块的起点」的上一项下标』除以 BB 刚好得到了「xx 所在块的编号」减一的值，所以有 id(x)=⌊x−1B⌋+1id(x) = \lfloor\frac{x - 1}{B}\rfloor + 1。
接下来的某个下标所在块的起终下标 cacl(x)cacl(x) 和 cacr(x)cacr(x)2 就好办了，直接套上 blkl(id(x))blkl(id(x)) 和 blkr(id(x))blkr(id(x)) 即可。
这一部分代码：
CPP
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 进阶建块

我们已经完成了基本的建块，考虑如何完成题目的操作。
首先看到操作 0\tt0：区间加。
那么我们想想，分了块，怎样才能优化加法？
肯定是把区间中的整块整体加，这里我们引入一个长度为块的数量的新数组：懒标记数组（lazy1∼⌈nB⌉lazy_{1\sim \lceil\frac{n}{B}\rceil}）。学过 SgT\tt SgT3 的童鞋们都知道这个东西。
转眼看操作 1\tt1：查询 [l,r][l, r] 中小于 c2c^2 的数的数量。
既然是查询不等式，看来得二分，那么我们还需要维护序列每块内的有序版本。唔。
所以建块的时候同时要初始化排序后的数组，如下图（红色是 lazylazy，紫色是原数组，蓝色是排序后数组）：
图二
进阶的建块例子
这部分代码如下：
CPP
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 区间加

若 opt=0\mathrm{opt} = 0，表示将位于 [l,r][l, r] 的之间的数字都加 cc。
首先考虑 ll，rr 在一个块内的情况（如 4,54,5）。此时暴力枚举 [l,r][l, r] 并加 cc（如 33）即可。结束后要重建整块。
图三
ll，rr 在一个块内的区间加
CPP
if (id(l) == id(r)) {
    for (int i = l; i <= r; i ++) { // 暴力枚举
        a[i] += c;
    }
    rebuild(id(l)); // 重构块
    return;
}
然后考虑 ll，rr 不在一个块内的情况（如 2,102,10）。
首先看 ll 和 rr 所在的块。这两个块不一定全部被查询区间覆盖，所以暴力枚举 [l,cacr(id(l))][l, cac\bold r(id(l))] 与 [cacl(id(r)),r][cac\bold l(id(r)), r] 并加 cc（如 44）即可。结束后要重建整块。
对于其间的整块，怎么用 lazylazy 呢？
其实很简单，直接枚举编号为 (id(l),id(r))(id(l), id(r))（即不包含两端块，因为它们是前文提到的散块已经计算过）的块，将它们的 lazylazy 加上 cc 即可。由于整块总体加数不会影响元素的相对大小，所以不重排。
看不懂？上图！
图四
ll，rr 在多个块内的区间加
这一部分代码：
CPP
for (int i = l; i <= cacr(l); i ++) { // 左边散块
    a[i] += c;
}
rebuild(id(l));
for (int i = id(l) + 1; i < id(r); i ++) { // 中间整块
    lzy[i] += c;
}
for (int i = cacl(r); i <= r; i ++) { // 右端散块
    a[i] += c;
}
rebuild(id(r));

0x03 区间查询

上文提到二分查询，那么具体怎么做捏？
同样要特判 ll，rr 在一个块的情况，不然会多算。
我们先看散块。散块由于未对应到排序后数组，所以只能暴力求出。注意判断时需要使用真实值。
然后是整块，使用 std::lower_bound 即可。由于 lower_bound 算的是第一个大于等于给出数的位置，所以要在减去数组地址的基础上减去一。正好 blklblkl 是一个块的第一个位置（不是第零个），所以直接减去 blkl(i)blkl(i) 即可。具体看下面的代码。
先放个例子（被 std::lower_bound 选中区域标记为了橄榄色，例子里面散块刚好没有懒惰的加所以就是真值）：
图五
区间查询例子
CPP
inl_force int query(int l, int r, Tp c) {
    Tp x = c * c;
    int ans = 0;
    if (id(l) == id(r)) { // 一定要特判
        for (int i = l; i <= r; i ++) {
            if (real(i) < x) { // 计算真值
                ans ++;
            }
        }
        return ans;
    }
    for (int i = l; i <= cacr(l); i ++) { // 左侧散块
        if (real(i) < x) { // 真值！
            ans ++;
        }
    }
    for (int i = id(l) + 1; i < id(r); i ++) { // 中间整块二分
        ans += lower_bound(sorted + blkl(i), // 块的左端
                           sorted + blkr(i) + 1, // 块的右端，注意左闭右开所以要加一
                           x - lzy[i]) - // 注意算 lazy，但是 原值 + lazy < x <=> 原值 < x - lazy 
               (sorted + blkl(i)); // 减去数组地址后，减去块的起始下标
    }
    for (int i = cacl(r); i <= r; i ++) { // 右侧散块
        if (real(i) < x) { // 真值！
            ans ++;
        }
    }
    return ans;
}

0x02 复杂度分析

两个操作都需要散块暴力，O(Blog⁡B)\mathcal{O}(B\log B)，也需要整块操作，假设在整个序列上操作，那么就是 O(nB)\mathcal{O}(\frac{n}{B})，为了均衡两者，所以块长 BB 约取 n\sqrt{n}。（当然你可以乱搞）

0x03 避坑指南

0x00 我遇到的

  1. 五个索引公式（id, cacl, cacr, blkl, blkr）别写错了
    最致命的一集。不要指望什么 x−xmod  Bx - x \mod B 之类的嘞。 除此之外，blkrblkr 一定要和 nn 取 min⁡\min！
  2. 不特判左右边界在一个块内的情况
    会整整多算一个区间（别指望减去多算的！lazy 可以为负，但是区间查询怎么减去一个区间的结果？）
  3. 重构的时候没有拷贝整个块
    想啥？希望一个元素在排序序列中有历史和最新版本共存吗？

0x01 极有可能遇到的

  1. 查询不取真值（没加 lazy） 另一个致命的，但是好调。

0x04 代码呈现

CPP
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long ll;
const int MAXN = 3e5 + 5, MAXB = 560;
ll a[MAXN];
#define inl_force __attribute__((always_inline)) inline // 强制编译器进行内联（勿喷，这个真的可以增加效率）

template <typename Tp> // 封装。需要开五个就老实了 AwA
struct BlkDeco {
    Tp a[MAXN] = {}, lzy[MAXB] = {}, sorted[MAXN] = {};
    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));
    }
    inl_force ll real(int x) {
        return lzy[id(x)] + a[x];
    }
    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);
        for (int i = 1; i <= id(n); i ++) {
            rebuild(i);
        }
    }
    inl_force void add(int l, int r, Tp c) {
        if (id(l) == id(r)) {
            for (int i = l; i <= r; i ++) {
                a[i] += c;
            }
            rebuild(id(l));
            return;
        }
        for (int i = l; i <= cacr(l); i ++) {
            a[i] += c;
        }
        rebuild(id(l));
        for (int i = id(l) + 1; i < id(r); i ++) {
            lzy[i] += c;
        }
        for (int i = cacl(r); i <= r; i ++) {
            a[i] += c;
        }
        rebuild(id(r));
    }
    inl_force int query(int l, int r, Tp c) {
        Tp x = c * c;
        int ans = 0;
        if (id(l) == id(r)) {
            for (int i = l; i <= r; i ++) {
                if (real(i) < x) {
                    ans ++;
                }
            }
            return ans;
        }
        for (int i = l; i <= cacr(l); i ++) {
            if (real(i) < x) {
                ans ++;
            }
        }
        for (int i = id(l) + 1; i < id(r); i ++) {
            ans += lower_bound(sorted + blkl(i),
                               sorted + blkr(i) + 1,
                               x - lzy[i]) -
                   (sorted + blkl(i));
        }
        for (int i = cacl(r); i <= r; i ++) {
            if (real(i) < x) {
                ans ++;
            }
        }
        return ans;
    }
};

BlkDeco<ll> S;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); // 实测关流速度比快读快写快？？
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    S.imp(n, a); // 导入
    for (int _ = 1; _ <= n; _ ++) {
        int op, l, r;
        ll c;
        cin >> op >> l >> r >> c;
        if (!op) {
            S.add(l, r, c);
        } else {
            cout << S.query(l, r, c) << '\n';
        }
    }
    return 0;
}

0x~1 后记

成文、画图不易，您的每一个赞都是激励我做的更多更好的信任！
若有问题欢迎在评论区提出。

0x~0 注释

Footnotes

  1. 「[图片]」本来这张图是一个 base64，但看着文章里多出的 10kb，我沉思着，还是放弃 base64 吧。 ↩
  2. 「cacl(x)cacl(x) 和 cacr(x)cacr(x)」凑活吧，想不出什么名字，就拿来了 calcuate\tt calcuate 一词。 ↩
  3. 线段树。 ↩

评论

共 15 条评论，欢迎与作者交流。

正在加载评论...