洛谷P1502 窗口的星星

题目背景

小卡买到了一套新房子，他十分的高兴，在房间里转来转去。

题目描述

晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户。

天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。

这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

输入格式

本题有多组数据，第一行为 TT，表示有 TT 组数据。

对于每组数据：

第一行 33 个整数 n,W,Hn,W,H 表示有 nn 颗星星，窗口宽为 WW，高为 HH。

接下来 nn 行，每行三个整数 x_i,y_i,l_ixi​,yi​,li​ 表示星星的坐标在 (x_i,y_i)(xi​,yi​)，亮度为 l_ili​。

输出格式

TT 个整数，表示每组数据中窗口星星亮度总和的最大值。

输入输出样例

输入 #1复制

2

3 5 4
1 2 3
2 3 2
6 3 1

3 5 4
1 2 3
2 3 2
5 3 1

输出 #1复制

5
6

说明/提示

小卡买的窗户框是金属做的，所以在边框上的不算在内。

数据范围

1\le T \le 101≤T≤10
1\le n \le 10^41≤n≤104
1\le W,H \le 10^61≤W,H≤106 0\le x_i,y_i < 2^{31}0≤xi​,yi​<231

上代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#define LL long long
#define N (100001)
using namespace std;
template <typename T> void read(T&t) {
	t=0;
	bool fl=true;
	char p=getchar();
	while (!isdigit(p)) {
		if (p=='-') fl=false;
		p=getchar();
	}
	do {
		(t*=10)+=p-48;p=getchar();
	}while (isdigit(p));
	if (!fl) t=-t;
}
int t,n,W,H,tot,cnt,maxans;
int left[N],right[N]; 
struct star{
	int x,y,l,id;
	bool fl;
}a[N],b[N];
struct node{
	int l,r,lazy,v;
}T[N<<2];
inline bool cmp(star a,star b){
	return a.x<b.x;
}
inline bool cmp1(star a,star b){
	return a.y==b.y?a.l>b.l:a.y<b.y;
}
void build(int u,int l,int r){
	T[u].lazy=T[u].v=0;
	T[u].l=l,T[u].r=r;
	if (l==r) return; 
	int mid=l+r>>1,kk=u<<1;
	build(kk,l,mid);
	build(kk|1,mid+1,r);
}
void pushdown(int u){
	if (T[u].lazy){
		int aa=T[u].lazy,kk=u<<1;
		T[u].lazy=0;
		T[kk].v+=aa;
		T[kk].lazy+=aa;
		T[kk|1].v+=aa;
		T[kk|1].lazy+=aa;
	}
}
int query(int u,int L,int R){
	if (L<=T[u].l&&T[u].r<=R) return T[u].v;
	pushdown(u);
	int ret=0,k=u<<1,mid=T[u].l+T[u].r>>1;
	if (L<=mid) ret=query(k,L,R);
	if (R>mid) ret=max(ret,query(k|1,L,R));
	return ret;
}
void add(int u,int L,int R,int k){
	if (L<=T[u].l&&T[u].r<=R){
		T[u].v+=k;
		T[u].lazy+=k;
		pushdown(u);
		return;
	}
	pushdown(u);
	int mid=T[u].l+T[u].r>>1,vv=u<<1;
	if (L<=mid) add(vv,L,R,k);
	if (R>mid) add(vv|1,L,R,k);
	T[u].v=max(T[vv].v,T[vv|1].v);
}
int main(){
	read(t);
	while (t--){
		cnt=tot=maxans=0;
		read(n),read(W),read(H);
		for (int i=1;i<=n;i++){
			read(a[i].x),read(a[i].y),read(a[i].l);
			a[i].id=i; a[i].fl=0;
			b[i].y=a[i].y,b[i].l=a[i].l;
			b[i].id=i;
		}
		tot=n;
		for (int i=1;i<=n;i++){
			a[++tot].x=a[i].x+W-1;
			a[tot].id=i;
			a[tot].fl=1;
		}
		sort(a+1,a+tot+1,cmp);
		for (int i=1;i<=tot;i++){
			int tt=0;
			if (a[i].x==a[i-1].x&&i!=1) tt=cnt;
			else tt=++cnt;
			if (!a[i].fl) left[a[i].id]=tt;
			else right[a[i].id]=tt;
		}
		tot=n;
		for (int i=1;i<=n;i++){
			b[++tot].y=b[i].y+H-1;
			b[tot].l=-b[i].l;
			b[tot].id=b[i].id;
		}
		sort(b+1,b+tot+1,cmp1);
		build(1,1,cnt);
		for (int i=1;i<=tot;i++){
			if (b[i].l>0){
				int num=query(1,left[b[i].id],right[b[i].id]);
				if (num+b[i].l>maxans) maxans=num+b[i].l;
			}
			add(1,left[b[i].id],right[b[i].id],b[i].l);
		}
		printf("%d\n",maxans);
	}
	return 0;
}