萌新扫描线10pts求调,AC on #1
查看原帖
萌新扫描线10pts求调,AC on #1
688596
dayz_break404楼主2024/7/17 20:17
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e4+20;
ll t,n,W,H,X[maxn],ans=-1;
struct smx{
	ll l,r,h,light;
	bool operator < (const smx &T) const{
		return h<T.h||(h==T.h&&light<T.light);
	}
}line[maxn];
struct segment{
	ll mx,tag;
}tree[maxn<<3];
struct semment_tree{
	inline ll ls(ll x){
		return x<<1;
	}
	inline ll rs(ll x){
		return x<<1|1;
	}
	inline void push_up(ll p){
		tree[p].mx=max(tree[ls(p)].mx,tree[rs(p)].mx);
	}
	void build(ll p,ll l,ll r){
		tree[p].tag=0; 
		if(l==r){
			tree[p].mx=0;
			return;
		}
		ll mid=l+r>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
		push_up(p);
	}
	inline void push_down(ll p){
		tree[ls(p)].mx+=tree[p].tag,tree[rs(p)].mx+=tree[p].tag;
		tree[ls(p)].tag+=tree[p].tag,tree[rs(p)].tag+=tree[p].tag;
		tree[p].tag=0;
	}
	void update(ll p,ll l,ll r,ll x,ll y,ll k){
		if(x<=X[l]&&y>=X[r+1]){
			tree[p].mx+=k,tree[p].tag+=k;
			return;
		}
		push_down(p);
		ll mid=l+r>>1;
		if(X[mid+1]>x) update(ls(p),l,mid,x,y,k);//mid端点的右侧 
		if(y>X[mid+1]) update(rs(p),mid+1,r,x,y,k);//mid+1端点的左侧 
		push_up(p);
	}
}S;
int main(){
	scanf("%lld",&t);
	ll x,y,z;
	while(t--){
	ans=-0x7fffffff;
	scanf("%lld%lld%lld",&n,&W,&H);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		X[i*2-1]=x,X[i*2]=x+W-1;
		line[i*2-1]=(smx){x,x+W-1,y,z},line[i*2]=(smx){x,x+W-1,y+H-1,-z};
	}
	n<<=1;
	sort(line+1,line+n+1);
	sort(X+1,X+n+1);
	ll tot=unique(X+1,X+n+1)-X-1;
	S.build(1,1,tot-1);
	for(int i=1;i<n;i++){
		S.update(1,1,n,line[i].l,line[i].r,line[i].light);
		ans=max(ans,tree[1].mx);
	}
	printf("%lld\n",ans);
	}
	return 0;
}
2024/7/17 20:17
加载中...