为什么这样写才能过
查看原帖
为什么这样写才能过
929819
HEIMOFA楼主2023/8/17 09:44
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
struct Line{
	int l,r,h,add;
}line[2*N];
struct Tree{
	int l,r;
	int add,mx;
}tree[16*N];
int X[2*N];

bool cmp(Line x,Line y){
	if(x.h==y.h) return x.add<y.add;
	return x.h<y.h;
}
void pushup(int key){
	tree[key].mx=max(tree[key*2].mx,tree[key*2+1].mx);
	return ;
}
void pushdown(int key){
	tree[key*2].add+=tree[key].add;
	tree[key*2+1].add+=tree[key].add;
	tree[key*2].mx+=tree[key].add;
	tree[key*2+1].mx+=tree[key].add;
	tree[key].add=0;
	return ;
}
void build(int key,int l,int r){
	tree[key]=(Tree){l,r,0,0};
	if(l==r) return ;
	int mid=l+r>>1;
	build(key*2,l,mid);
	build(key*2+1,mid+1,r);
	return ;
}
void add(int key,int l,int r,int k){
	if(tree[key].r<l||tree[key].l>r) return ;
	if(tree[key].l>=l&&tree[key].r<=r){
		tree[key].add+=k;
		tree[key].mx+=k;
		return ;
	}
	pushdown(key);
	add(key*2,l,r,k);
	add(key*2+1,l,r,k);
	pushup(key);
	return ;
}
signed main()
{
	int t;scanf("%lld",&t);
	while(t--){
		int n,w,h;
		scanf("%lld%lld%lld",&n,&w,&h);
		for(int i=1;i<=n;i++){
			int x,y,l;
			scanf("%lld%lld%lld",&x,&y,&l);
			X[2*i-1]=x,X[2*i]=x+w;
			line[2*i-1]=(Line){x,x+w,y,l};//就是这里
			line[2*i]=(Line){x,x+w,y+h,-l};
		}
		n*=2;
		sort(X+1,X+n+1);
		sort(line+1,line+n+1,cmp);
		int cnt=unique(X+1,X+n+1)-X-1;
		build(1,1,cnt-1);
		int ans=0;
		for(int i=1;i<=n;i++){
			int l=lower_bound(X+1,X+cnt+1,line[i].l)-X;
			int r=lower_bound(X+1,X+cnt+1,line[i].r)-X;
			add(1,l,r-1,line[i].add);
			ans=max(ans,tree[1].mx);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
2023/8/17 09:44
加载中...