勐海县住房和城乡建设局网站,大业推广网站,会议专属网站平台建设报价单,计算机科学专业就业方向在一个星光摧残的夜晚#xff0c;蒜头君一颗一颗的数这天上的星星。蒜头君给在天上巧妙的画了一个直角坐标系#xff0c;让所有的星星都分布在第一象。天上有 nn 颗星星#xff0c;他能知道每一颗星星的坐标和亮度。现在#xff0c;蒜头君问自己 qq 次#xff0c;每次他问…
在一个星光摧残的夜晚蒜头君一颗一颗的数这天上的星星。蒜头君给在天上巧妙的画了一个直角坐标系让所有的星星都分布在第一象。天上有 nn 颗星星他能知道每一颗星星的坐标和亮度。现在蒜头君问自己 qq 次每次他问自己每个矩形区域的星星的亮度和是多少包含边界上的星星。输入格式第一行输入一个整数 n(1 \le n \le 50000)n(1≤n≤50000) 表示星星的数量。接下里 nn 行每行输入三个整数 x,y,w(0 \le x, y, w\le 2000)x,y,w(0≤x,y,w≤2000)表示在坐标 (x,y)(x,y) 有一颗亮度为 ww 的星星。注意一个点可能有多个星星。接下来一行输入一个整数 q(1 \le q \le 50000)q(1≤q≤50000)表示查询的次数。接下来 qq 行每行输入四个整数 x_1, y_1, x_2, y_2x1,y1,x2,y2其中 (x_1, y_1)(x1,y1) 表示查询的矩形的左下角的坐标(x_2, y_2)(x2,y2) 表示查询的矩形的右上角的坐标0 \le x_1 \le x_2 \le 20000≤x1≤x2≤20000 \le y_1 \le y_2 \le 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给出第一象限下的坐标并给出这个坐标下的值 给我们多个矩形的范围 求这个
虽然暴力能过
但是树状数组 也可以~并且更快~
复杂度O(q*log(x)*log(y))
x,y2000
注意边界要算进去 而且数据不能存在0,0上
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll tre[2010][2010];
void add(int x,int y,int w)
{for(int ix;i2001;ii(-i)){for(int jy;j2001;jj(-j)){tre[i][j]w;}
}
ll query(int x,int y){ll sum0;for(int ix;i0;i-i(-i)){for(int jy;j0;j-j(-j)){sumtre[i][j]; }return sum;
}
int main()
{int n;ios::sync_with_stdio(0);cinn;while(n--){int x,y,w;cinxyw;add(x1,y1,w);}int q;cinq;while(q--){int lx,ly,rx,ry;cinlxlyrxry;ll ans query(rx1,ry1)-query(rx1,ly)-query(lx,ry1)query(lx,ly); //注意边要算在矩形内 coutansendl; }return 0;
}
