守墓人(Tomb Keeper) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

struct RangeBIT {
    int n;
    vector<long long> b1, b2;
    RangeBIT(int n) : n(n), b1(n + 2, 0), b2(n + 2, 0) {}
    void add(int idx, long long v) {
        long long v2 = v * idx;
        for (int i = idx; i <= n; i += i & -i) {
            b1[i] += v;
            b2[i] += v2;
        }
    }
    void rangeAdd(int l, int r, long long v) {
        add(l, v);
        add(r + 1, -v);
    }
    long long prefixSum(int idx) const {
        long long s1 = 0, s2 = 0;
        for (int i = idx; i > 0; i -= i & -i) {
            s1 += b1[i];
            s2 += b2[i];
        }
        return (idx + 1) * s1 - s2;
    }
    long long rangeSum(int l, int r) const {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, f;
    if (!(cin >> n >> f)) return 0;
    RangeBIT bit(n);
    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        bit.rangeAdd(i, i, a);
    }
    for (int i = 0; i < f; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long k;
            cin >> l >> r >> k;
            bit.rangeAdd(l, r, k);
        } else if (op == 2) {
            long long k;
            cin >> k;
            bit.rangeAdd(1, 1, k);
        } else if (op == 3) {
            long long k;
            cin >> k;
            bit.rangeAdd(1, 1, -k);
        } else if (op == 4) {
            int l, r;
            cin >> l >> r;
            cout << bit.rangeSum(l, r) << "\n";
        } else {
            cout << bit.rangeSum(1, 1) << "\n";
        }
    }
    return 0;
}