天上的星星

发表于 | 分类于 ， ， | 阅读数 次

链接:天上的星星

Description

  • 在一个星光摧残的夜晚，蒜头君一颗一颗的数这天上的星星。
  • 蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有 n 颗星星，他能知道每一颗星星的坐标和亮度。
  • 现在，蒜头君问自己 q 次，每次他问自己每个矩形区域的星星的亮度和是多少（包含边界上的星星）。

    Input

  • 第一行输入一个整数n(1≤n≤50000)，表示星星的数量。
  • 接下来n行，每行输入三个整数x,y,w(0≤x,y,w≤2000)，表示在坐标(x,y)有一颗亮度为w的星星。注意一个点可能有多个星星。
  • 接下来一行输入一个整数q(1≤q≤50000)，表示查询的次数。
  • 接下来q行，每行输入四个整数x1,y1,x2,y2，其中(x1,y1)表示查询的矩形的左下角的坐标，(x2,y2)表示查询的矩形的右上角的坐标，
  • 0≤x1≤x2≤2000，0≤y1≤y2≤2000。

    Output

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

    Sample Input

    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

    Sample Output

    7
    32
    8
    0

    题解

  • 容斥原理加前缀和，水题，傻逼地写了个n颗线段树维护。。。
  • 答案是dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]
  • 计算dp的时候，维护每行的前缀和，然后dp[i][j]=dp[i-1][j]+tp[i][j];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=3000;
int dp[N][N],tp[N][N],g[N][N],q,n;

int main(){
    scanf("%d",&n);
    rep(i,1,n){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        g[x+1][y+1]+=w;     //注意这里是+=   有可能给出重复的点
    }
    rep(i,1,2001)rep(j,1,2001){
        tp[i][j]=tp[i][j-1]+g[i][j];	//第i行1-j列的和 
        dp[i][j]=dp[i-1][j]+tp[i][j];
    }
    scanf("%d",&q);
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1++;y1++;x2++;y2++;
        printf("%d\n",dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);
    }
    return 0;
}