题解：P13976 数列分块入门 1

Eric998 · 2025-09-10 14:51:19 · 题解

跑的飞块。5e5 250ms。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1 << 19], B[1 << 10], n, q;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], B[i >> 10] += a[i];
    while (q--) {
        int op, l, r, L, R, res = 0;
        cin >> op >> l >> r;
        if (op == 1)
            a[l] += r, B[l >> 10] += r;
        else {
            L = l >> 10, R = r >> 10;
            if (L ^ R) {
                for (int i = l; i < (L + 1) << 10; i++)
                    res += a[i];
                for (int i = L + 1; i < R; i++)
                    res += B[i];
                for (int i = R << 10; i <= r; i++)
                    res += a[i];
            } else
                for (int i = l; i <= r; i++)
                    res += a[i];
            cout << res << '\n';
        }
    }
}