RE3个点求调
查看原帖
RE3个点求调
763878
Jerry_heng楼主2023/8/16 17:44
#include<bits/stdc++.h>
#define int long longa
using namespace std;
const int mxn=1e5+10;
int n,w,h,t,a[mxn<<1],cnt,mx[mxn<<2],laz[mxn<<2],ans;
struct node{
	int y1,y2,x,val;
}tree[mxn<<2];
bool cmp(node x,node y){
	return x.x<y.x||x.x==y.x&&x.val>y.val;
}
int query(int x){
	return lower_bound(a+1,a+n+1,x)-a;
}
void pushdown(int o){
	laz[o*2]+=laz[o],laz[o*2+1]+=laz[o];
	mx[o*2]+=laz[o],mx[o*2+1]+=laz[o];
	laz[o]=0;
}
void update(int o,int l,int r,int L,int R,int v){
	if(L<=l&&r<=R){
		laz[o]+=v;
		mx[o]+=v;
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	if(L<=mid)update(o*2,l,mid,L,R,v);
	if(R>mid)update(o*2+1,mid+1,r,L,R,v);
	mx[o]=max(mx[o*2],mx[o*2+1]);
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		ans=0;
		memset(laz,0,sizeof laz);
		memset(mx,0,sizeof mx);
		scanf("%lld%lld%lld",&n,&w,&h);
		for(int i=1;i<=n;i++){
			int x,y,v;
			scanf("%lld%lld%lld",&x,&y,&v);
			a[i*2-1]=y,a[i*2]=y+h-1;
			tree[i*2-1]=(node){y,y+h-1,x,v};
			tree[i*2]=(node){y,y+h-1,x+w-1,-v};
		}
		n<<=1;
		sort(a+1,a+n+1);
		sort(tree+1,tree+n+1,cmp);
		cnt=unique(a+1,a+n+1)-a-1;
		for(int i=1;i<=n;i++){
			update(1,1,cnt,query(tree[i].y1),query(tree[i].y2),tree[i].val);
			ans=max(ans,mx[1]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
2023/8/16 17:44
加载中...