分块

原理

见《进阶指南》第224页。

模板题

AcWing-243-一个简单的整数问题2

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

typedef long long LL;
const int N = 100010, T = 320;
int n, m;
LL a[N];
int pos[N], L[T], R[T];
LL sum[T], add[T]; // info

void initialize () {
    int t = sqrt(n);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
    }
    if (R[t] < n) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }

    for (int i = 1; i <= t; ++ i) {
        for (int j = L[i]; j <= R[i]; ++ j) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
}
void modify (int l, int r, LL val) {
    int x = pos[l], y = pos[r];
    if (x == y) {
        for (int i = l; i <= r; ++ i) a[i] += val;
        sum[x] += val * (r - l + 1);
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) add[i] += val;
        for (int i = l; i <= R[x]; ++ i) a[i] += val;
        sum[x] += val * (R[x] - l + 1);
        for (int i = L[y]; i <= r; ++ i) a[i] += val;
        sum[y] += val * (r - L[y] + 1);
    }
}
LL query (int l, int r) {
    int x = pos[l], y = pos[r];
    LL res = 0;
    if (x == y) {
        for (int i = l; i <= r; ++ i) res += a[i];
        res += add[x] * (r - l + 1);
    } else {
        for (int i = x + 1; i <= y - 1; ++ i)
            res += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[x]; ++ i) res += a[i];
        res += add[x] * (R[x] - l + 1);
        for (int i = L[y]; i <= r; ++ i) res += a[i];
        res += add[y] * (r - L[y] + 1);
    }
    return res;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);

    initialize();
    while (m --) {
        char opt[5];
        scanf("%s", opt);
        if (opt[0] == 'C') {
            int l, r, val;
            scanf("%d%d%d", &l, &r, &val);
            modify(l, r, val);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", query(l, r));
        }
    }
    return 0;
}