题意
T组数据，每次给你n个点，含点权
给你一个矩形，只能底边平行x轴放置
求矩形内点权和的最大值
T≤10,n≤1e5
分析
首先，看到n和xy的范围，想到离散化
其次， 我们求的是一个框框（范围）内的东西， 特别是有扫描线，且能够出入，所以想到线段树
（有点牵强...主要是因为我们做的就是线段树题目...
想想怎么实现，怎么做题
因为是一个框框，它框住某点的位置有多个，这样不好维护线段树，所以
我们把每个点(i,j)作为左下角，向右向上延生至(i+w-1,j+h-1)，这个矩形加上(i,j)的贡献（即亮度 ）（注：不包括边框）
不考虑横坐标，它能影响到的矩形为:y到y+h的点所代表的所有矩形。
考虑上横坐标，用扫描线，及时删除不在当前横坐标能覆盖的星星。
参考代码&分析
https://www.luogu.org/blog/HotoChino/solution-p1502
错误代码（留坑代填（wtm做了一下午....还是没有找到错误
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 10000+9
int n,w,h;
int mx[MAX<<3], day[MAX<<1], addv[MAX<<2];//Discrete Array y 离散化y数组
//线段树四倍，扫描线两倍
struct seg{//平行于y轴的扫描线
int x, y1, y2, l;
seg(int x=0, int y1=0, int y2=0, int l=0) : x(x), y1(y1), y2(y2), l(l) {}
bool operator < (const seg& xxx) const {
return x < xxx.x;//从左向右， 按顺序扫， 所以需要排序
}
} s[MAX<<1];
struct node{
int x, y, l;
bool operator < (const node& xxx) const {
return x < xxx.x ;
}
}a[MAX];
void push_up(int o) { mx[o] = max(mx[o<<1], mx[o<<1|1]); }
void pushtag(int o, int l, int r, int v) { addv[o] += v, mx[o] += v;};
void push_down(int o, int l, int r) {
if(addv[o] == 0) return ;
addv[o<<1] += addv[o];
mx[o<<1] += addv[o];
addv[o<<1|1] += addv[o];
mx[o<<1|1] += addv[o];
addv[o] = 0;
}
void optdate(int o, int l, int r, int ql, int qr, int v) {
if(ql <= l && r <= qr) { pushtag(o, l, r, v); return ;}
push_down(o, l, r);
int mid = (l+r)>>1;
if(ql <= mid) optdate(o<<1, l, mid, ql, qr, v);
if(qr > mid) optdate(o<<1|1, mid+1, r, ql, qr, v);
push_up(o);
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d", &n, &w, &h);
memset(mx, 0, sizeof(mx));
memset(day, 0, sizeof(day));
int x,y,l;
for(int i = 1; i <= n; i++) {
scanf("%d%d%d",&x,&y,&l);//亮度l
s[i] = seg(x, y, y+h-1, l);
day[i] = y;
s[i+n] = seg(x+w-1, y, y+h-1, -l);//-l表示出
day[i+n] = y+h-1;
}
n <<= 1;//两倍
sort(day+1, day+1+n);
int tot = 1;
for(int i = 2; i <= n; i++) if(day[i] != day[tot]) day[++tot] = day[i];
/*unique的使用：
sort(day+1,day+1+n);//排序
int tot=unique(day+1,day+1+n)-day-1;//去重 */
sort(s+1,s+1+n);//根据横坐标排序
//build();刚开始就是空的
int ans = 0;
for(int i = 1; i <= n; i++) {
int l = lower_bound(day+1, day+1+tot, s[i].y1 ) - day;//二分查找边界
int r = lower_bound(day+1, day+1+tot, s[i].y2 ) - day;//找到y1和y2,求出区间最大值
if(l > r) swap(l, r);
optdate(1, 1, tot, l, r, s[i].l );//下次再扫到右边界时就会在原区间加上-l，即删除； //
ans = max(ans, mx[1]);
}
printf("%d
",ans);
}
}