啊,救我 70分
查看原帖
啊,救我 70分
233027
fengwu楼主2021/10/28 15:02
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fxt(i,x,y) for(int i=(x);i<=(y);i++)
#define pyt(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e4+5;
int T,n,w,h,ans;
struct matrix{int xl,yl,xr,yr,val;}sca[N];
int lsh[N*2],lh;
struct scan{
	int x,l,r,val;
	scan(){}
	scan(int a,int b,int c,int d){x=a;l=b;r=c;val=d;}
	bool operator < (scan a)const{
		if(x==a.x)return val>a.val;
		return x<a.x;
	}
}now[N*2];
struct XDS{
	#define ls x<<1
	#define rs x<<1|1
	int mx[N*8],tg[N*8];
	void pushup(int x){
		mx[x]=max(mx[ls],mx[rs]);
		return ;
	}
	void pushdown(int x){
		tg[ls]+=tg[x];
		tg[rs]+=tg[x];
		mx[ls]+=tg[x];
		mx[rs]+=tg[x];
		tg[x]=0;return ;
	}
	void build(int x,int l,int r){
		mx[x]=tg[x]=0;
		if(l==r)return ;
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		return ;
	}
	void ins(int x,int l,int r,int ql,int qr,int v){
		if(ql<=l&&r<=qr){
			mx[x]+=v;tg[x]+=v;
			return ;
		}
		if(tg[x])pushdown(x);
		int mid=l+r>>1;
		if(ql<=mid)ins(ls,l,mid,ql,qr,v);
		if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
		pushup(x);return ;
	}
	#undef ls
	#undef rs
}xds;
signed main(){
	scanf("%lld",&T);
	while(T--){
		lh=ans=0;
		scanf("%lld%lld%lld",&n,&w,&h);
		fxt(i,1,n){
			scanf("%lld%lld%lld",&sca[i].xl,&sca[i].yl,&sca[i].val);
			sca[i].xr=sca[i].xl+w-1;
			sca[i].yr=sca[i].yl+h+1;
			now[i*2-1]=scan(sca[i].xl,sca[i].yl,sca[i].yr,sca[i].val);
			now[i*2]=scan(sca[i].xr,sca[i].yl,sca[i].yr,-sca[i].val);
			lsh[++lh]=sca[i].yl,lsh[++lh]=sca[i].yr;
		}
		sort(lsh+1,lsh+lh+1);lh=unique(lsh+1,lsh+lh+1)-lsh-1;
		sort(now+1,now+2*n+1);
		xds.build(1,1,lh);
		fxt(i,1,2*n){
			ans=max(ans,xds.mx[1]);
			now[i].l=lower_bound(lsh+1,lsh+lh+1,now[i].l)-lsh;
			now[i].r=lower_bound(lsh+1,lsh+lh+1,now[i].r)-lsh;
			xds.ins(1,1,lh,now[i].l,now[i].r,now[i].val);
		}ans=max(ans,xds.mx[1]);
		printf("%lld\n",ans);
	}
}
2021/10/28 15:02
加载中...