题解：P13979 数列分块入门 4

Chase12345 · 2025-09-07 00:54:18 · 题解

这道题就是 P3371。

区间加的做法

分成整块和散块。

整块直接在 tag 上处理就行。

散块暴力加。

区间和的做法

分成整块和散块。

注意整块除了加上区间和之外还要加上 tag 乘上区间长度。这是显然地。

散块暴力加然后加上 tag。

复杂度分析

显然每次操作都是 O(b+\frac{n}{b})，取 b=\sqrt n 最优，则复杂度均摊为 O(\sqrt n)，总复杂度为 O(q \sqrt n)。

代码

注意略带卡常。不要边算边取模。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int N = 300005, M = 1005;
int n, sizb, cntb;
i64 a[N], belong[N], l[M], r[M], add[M], sum[M];

void build() {
    sizb = sqrt(n);
    cntb = (n + sizb - 1) / sizb;
    for (int i = 1; i <= cntb; i++) {
        l[i] = (i - 1) * sizb + 1;
        r[i] = min(n, i * sizb);
        add[i] = 0;
        sum[i] = 0;
        for (int j = l[i]; j <= r[i]; j++)
            belong[j] = i, sum[i] += a[j];
    }
}

void update(int lft, int rght, i64 c) {
    int bl = belong[lft], br = belong[rght];
    if (bl == br) {
        for (int i = lft; i <= rght; i++)
            a[i] += c, sum[bl] += c;
    } else {
        for (int i = lft; i <= r[bl]; i++)
            a[i] += c, sum[bl] += c;
        for (int i = bl + 1; i < br; i++)
            add[i] += c, sum[i] += c * (r[i] - l[i] + 1);
        for (int i = l[br]; i <= rght; i++)
            a[i] += c, sum[br] += c;
    }
}

i64 query(int lft, int rght, i64 mod) {
    int bl = belong[lft], br = belong[rght];
    i64 res = 0;
    if (bl == br)
        for (int i = lft; i <= rght; i++)
            res = res + a[i] + add[bl];
    else {
        for (int i = lft; i <= r[bl]; i++)
            res = res + a[i] + add[bl];
        for (int i = bl + 1; i < br; i++)
            res = res + sum[i];
        for (int i = l[br]; i <= rght; i++)
            res = res + a[i] + add[br];
    }
    return (res % mod + mod) % mod;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build();
    for (int i = 1; i <= n; i++) {
        int op, l, r;
        i64 c;
        cin >> op >> l >> r >> c;
        if (!op) update(l, r, c);
        else cout << query(l, r, c + 1) << '\n';
    }
    return 0;
}