【马蜂良好】裸的二维树状数组求条
查看原帖
【马蜂良好】裸的二维树状数组求条
846661
ARIS1_0楼主2024/10/12 16:09
int n, m, a, b, c, d, delta;
char op;
int lowbit(int x) {
    return x & (-x);
}
int t[2105][2105][4];
void add(int tagx, int tagy, int k) {
    for (int i = tagx; i <= n; i += lowbit(i)) {
        for (int j = tagy; j <= m; j += lowbit(i)) {
            t[i][j][0] += k;
            t[i][j][1] += k * tagx;
            t[i][j][2] += k * tagy;
            t[i][j][3] += k * tagx * tagy;
        }
    }
}
void update(int stx, int sty, int edx, int edy, int k) {
    add(stx, sty, k);
    add(stx, edy + 1, -k);
    add(edx + 1, sty, -k);
    add(edx + 1, edy + 1, k);
}
int sum(int x, int y) {
    int ret = 0;

    for (int i = x; i; i -= lowbit(i)) {
        for (int j = y; j; j -= lowbit(j)) {
            ret += (x + 1) * (y + 1) * t[i][j][0] - (y + 1) * t[i][j][1] - (x + 1) * t[i][j][2] + t[i][j][3];
        }
    }

    return ret;
}
int Q(int stx, int sty, int edx, int edy) {
    return sum(edx, edy) - sum(stx - 1, edy) - sum(edx, sty - 1) + sum(stx - 1, sty - 1);
}
int main() {
    cin >> op;
    n = read();
    m = read();

    while (cin >> op) {
        a = read();
        b = read();
        c = read();
        d = read();

        if (op == 'L') {
            delta = read();
            update(a, b, c, d, delta);
        } else {
            write(Q(a, b, c, d));
            putchar('\n');
        }
    }

    return 0;
}
2024/10/12 16:09
加载中...