#7不过?求调
查看原帖
#7不过?求调
540615
dongyc0301楼主2022/7/6 16:53

#include <bits/stdc++.h>
using namespace std;
int n,w,h,len; 
long long y[20005];
struct square
{
	long long int x,y1,y2;int k;
}s[20005];
struct seg
{
	long long int l,r;int dat,add;
}t[80005];
int val(long long int x)
{
	return lower_bound(y+1,y+1+len,x)-y;
}
bool cmp(square x,square y)
{
	return x.x<y.x; 
}
void build(int p,int l,int r)
{
	t[p].l=l;t[p].r=r;t[p].dat=0;t[p].add=0;
	if(l==r)
		return ;
	int mid=(l+r)/2;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
}
void spread(int p)
{
	if(t[p].add)
	{
		t[p*2].add+=t[p].add;
		t[p*2].dat=t[p*2].dat+t[p].add;
		t[p*2+1].add+=t[p].add;
		t[p*2+1].dat+=t[p].add;
		t[p].add=0;
	}
}
void change(int p,int l,int r,int k)
{
	if(t[p].l>=l&&t[p].r<=r)
	{
		t[p].add+=k;
		t[p].dat=t[p].dat+k;
		return ;
	}
	spread(p); 
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid)
		change(p*2,l,r,k);
	if(r>mid)
		change(p*2+1,l,r,k); 
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
} 
int main()
{
	int T;cin>>T;
	while(T--)
	{
		cin>>n>>w>>h;
		int i,j;
		for(i=1;i<=n;i++)
		{
			long long int x,yy;int c;cin>>x>>yy>>c;
			//x,y x+w-1,
			s[i].x=x;s[i+n].x=x+w-1;
			s[i].y1=s[i+n].y1=yy;
			s[i].y2=s[i+n].y2=yy+h-1;
			s[i].k=c;s[i+n].k=-c;
			y[i]=yy;y[i+n]=yy+h-1;
		} 
		sort(s+1,s+2*n+1,cmp);
		sort(y+1,y+2*n+1);len=unique(y+1,y+2*n+1)-y-1;
		
		build(1,1,len); 
		
		int maxn=-INT_MAX;
		for(i=1;i<=2*n;i++)
		{
			/*cout<<"round\n";
			cout<<i<<' '<<s[i].x<<' '<<s[i].y1<<' '
			<<s[i].y2<<" "<<s[i].k<<" "<<t[1].dat<<endl;*/
			change(1,val(s[i].y1),val(s[i].y2),s[i].k);
			//cout<<t[1].dat<<endl;
			maxn=max(maxn,t[1].dat);
		}
		cout<<maxn<<endl;
	}
	return 0;
}
2022/7/6 16:53
加载中...