题解：P13976 数列分块入门 1

yangjinqian · 2025-09-11 14:52:11 · 题解

题意

给一个长度为 n 的数列，以及 n 次操作，每次操作读入 opt、l、r、c。

• 若 opt = 0 表示将位于 [l, r] 的之间的数字都加 c。

• 若 opt = 1 表示询问 a_{r} 的值。

思路

虽然但是这个题可以用线段树或者树状数组做，但因为名字所以就用分块了。

基本思想：分块是一种暴力数据结构，它将数列分成 \lfloor \sqrt{n} + 0.5 \rfloor 个块，长度为 \sqrt{n}，特殊的，最后一个块长度可能小于 \sqrt{n}。设每个下标所在块的编号为 id_{i}。再设一个 add 数组，类似线段树的懒标记，表示每一个块总共加了多少。

对于修改，将 l 至 l 的块的右端点，和 r 的块的右端点至 r 进行暴力加法，而从 id_{l} + 1 到 id_{r} - 1 的块，让他们的 add 都加上 c。

对于询问，答案就是这个位置在当前数列中的值，加上它所在区间的 add 即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10;
ll n, len;
ll a[N], id[N], add[N];
void modify(ll l, ll r, ll c){
    if (id[l] == id[r]){
        for (ll i = l; i <= r; i++) a[i] += c;
        return;
    }
    for (ll i = l; i <= min(id[l] * len, n); i++) a[i] += c;
    for (ll i = id[l] + 1; i < id[r]; i++) add[i] += c;
    for (ll i = min(id[r] * len - len + 1, n); i <= r; i++) a[i] += c;
}
int main(){
    cin >> n;
    len = sqrt(n);
    for (ll i = 1; i <= n; i++) cin >> a[i], id[i] = (i - 1) / len + 1;
    for (ll i = 1; i <= n; i++){
        ll op, l, r, c;
        cin >> op >> l >> r >> c;
        if (!op) modify(l, r, c);
        else cout << a[r] + add[id[r]] << endl;
    }
}