计蒜客 - 天上的星星 (二维前缀和)

在一个星光摧残的夜晚，蒜头君一颗一颗的数这天上的星星。

蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有 nn 颗星星，他能知道每一颗星星的坐标和亮度。

现在，蒜头君问自己 qq 次，每次他问自己每个矩形区域的星星的亮度和是多少（包含边界上的星星）。

​​

输入格式

第一行输入一个整数 n(1≤n≤50000) 表示星星的数量。

接下里 n 行，每行输入三个整数 x,y,w(0≤x,y,w≤2000)，表示在坐标 (x,y) 有一颗亮度为 ww 的星星。注意一个点可能有多个星星。

接下来一行输入一个整数 q(1≤q≤50000)，表示查询的次数。

接下来 qq 行，每行输入四个整数 x1,y1,x2,y2，其中 (x1,y1) 表示查询的矩形的左下角的坐标(x2,y2) 表示查询的矩形的右上角的坐标，20000≤x1≤x2≤2000， 20000≤y1≤y2≤2000。

输出格式

对于每一次查询，输出一行一个整数，表示查询的矩形区域内的星星的亮度总和。

样例输入复制

5 5 0 6 7 9 7 8 6 13 9 7 1 3 0 19 4 0 8 7 9 0 0 7 10 2 7 10 9 5 4 7 5

样例输出复制

7 32 8 0

题解:  裸的二维前缀和 (求蓝色区域), 处理处理边界, 下图中的粉色粗线最后查询时不能减去这条线上的 . 

#include <iostream>
#include <cstdio>
using namespace std ;
const int MAX = 5010 ;
int a[MAX][MAX] ;
int main(){
    int n ;
    cin >> n ;
    int xb = 0 ; //
    int yb = 0 ;
    for(int i = 1 ;i<=n ;i++ ){
        int x ,y ,w ;
        cin >>x >>y >>w ;
        x++ ;
        y++ ;
        xb = max(xb,x) ;
        yb = max(yb,y);
        a[x][y]+=w ; // 一个点可能有多个星星
    }
    for(int i = 1 ; i<=2001 ; i++ ) {
        for(int j = 1 ;j<=2001 ; j++ ){
            a[i][j] +=a[i-1][j] + a[i][j-1] -a[i-1][j-1] ;
        }
    }
    
    int q ;
    cin >>q;
    while(q--){
        int x1,y1 , x2,y2 ;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1++ ;
        y1++ ;
        x2++ ;
        y2++ ;
        int ans = a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1] ;
        printf("%d\n",ans);
    }
    return 0 ;
}