计蒜客

二维差分,理论上很简单,虽然我实际上做的时候一堆问题

1.边界的星星包含在内,需要在减去的时候往前挪一个

2.我是从0开始的,循环的时候非常不方便

3.x1, x2, y1, y2总是弄混

#include <cstdio>
using namespace std;
const int N = 2001;
int sum[N][N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        sum[x][y] += w;
    }
    for (int i = 1; i < N; i++) {
        sum[i][0] = sum[i][0] + sum[i - 1][0];
        sum[0][i] = sum[0][i] + sum[0][i - 1];
    }

    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            sum[i][j] = sum[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    int q;
    scanf("%d", &q);
    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        int ans;
        if (x1 > 0 && y1 > 0)
            ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
        else if (x1 == 0 && y1 != 0)
            ans = sum[x2][y2] - sum[x2][y1 - 1];
        else if (x1 > 0)
            ans = sum[x2][y2] - sum[x1 - 1][y2];
        else
            ans = sum[x2][y2];
        printf("%d
", ans);
    }
    return 0;
}