20pts求助!!码风还行
查看原帖
20pts求助!!码风还行
1074879
Pandyyyds楼主2025/8/5 11:58
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+10;
struct Node{
	int l,r,mx,lazy;//lazy只是用来记录最大值的变化 
}tree[N*8];
int X[N];

struct line{
	int x1,x2,y;
	int tag;
	bool operator < (line &b){
		return y<b.y;
	}
}a[N*2];

void init(){
	memset(a,0,sizeof(a));
	memset(tree,0,sizeof(tree));
	memset(X,0,sizeof(X));
}
int n,w,h;

void build(int i,int l,int r){
	tree[i]={l,r,0,0};
	if(l==r) return;
	int mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
}

void pushdown(int i){
	tree[i].mx+=tree[i].lazy;
	if(tree[i].l!=tree[i].r){
		tree[i*2].lazy+=tree[i].lazy;
		tree[i*2+1].lazy+=tree[i].lazy;
	}
	tree[i].lazy=0;
}

void pushup(int i){
	tree[i].mx=max(tree[i*2].mx,tree[i*2+1].mx);
}

void change(int i,int l,int r,int tag){
	if(tree[i].l>r||tree[i].r<l) return;
	pushdown(i);
	if(l<=tree[i].l&&tree[i].r<=r){
		tree[i].lazy+=tag;
		pushdown(i);
		return;
	}
	change(i*2,l,r,tag),change(i*2+1,l,r,tag);
	pushup(i);
}


signed main(){
	freopen("in.txt","r",stdin); 
	int t;cin >> t;
	while(t--){
		init();
		cin >> n >> w >> h;
		for(int i=1;i<=n;i++){
			int x,y,l;cin >> x >> y >> l;
			a[i]={x,x+w-1,y,l};
			a[i+n]={x,x+w-1,y+h-1,-1*l};
			X[i]=x,X[i+n]=x+w-1;
		}
		n*=2;
		sort(a+1,a+1+n);
		sort(X+1,X+1+n);
		int s=unique(X+1,X+1+n)-X-1;
		build(1,1,s);
		int ans=-1;
		for(int i=1;i<=n;i++){
			int l=lower_bound(X+1,X+1+s,a[i].x1)-X;
			int r=lower_bound(X+1,X+1+s,a[i].x2)-X;
			change(1,l,r-1,a[i].tag);
			ans=max(ans,tree[1].mx);
		}
		cout << ans << "\n";
	}
	
}

2025/8/5 11:58
加载中...