洛谷P2357 守墓人 題解 數列分塊

題目連結：​​https://www.luogu.com.cn/problem/P2357​​

涉及操作：

1. 區間更新；
2. 單點更新（直接算到區間更新裡面）；
3. 區間查詢；
4. 單點查詢（直接算到區間查詢裡面）。

解題思路：

數列分塊。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
int n, m, blo, bl[maxn];
long long a[maxn], sum[505], tag[505];

void add(int l, int r, long long k) {
    for (int i = l; i <= min(r, bl[l]*blo); i ++)
        a[i] += k, sum[bl[i]] += k;
    if (bl[l] != bl[r]) {
        for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
            a[i] += k, sum[bl[i]] += k;
    }
    for (int i = bl[l]+1; i < bl[r]; i ++)
        tag[i] += k;
}

long long query(int l, int r) {
    long long res = 0;
    for (int i = l; i <= min(r, bl[l]*blo); i ++)
        res += a[i] + tag[bl[i]];
    if (bl[l] != bl[r]) {
        for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
            res += a[i] + tag[bl[i]];
    }
    for (int i = bl[l]+1; i < bl[r]; i ++)
        res += sum[i] + tag[i] * blo;
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    blo = sqrt(n);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        bl[i] = (i - 1) / blo + 1;
        sum[bl[i]] += a[i];
    }
    while (m --) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r; long long k;
            cin >> l >> r >> k;
            add(l, r, k);
        }
        else if (op == 2) {
            long long k;
            cin >> k;
            add(1, 1, k);
        }
        else if (op == 3) {
            long long k;
            cin >> k;
            add(1, 1, -k);
        }
        else if (op == 4) {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << endl;
        }
        else { // op == 5
            cout << query(1, 1) << endl;
        }
    }
    return 0;
}