MnZn求助,只ac#1,码风好看
查看原帖
MnZn求助,只ac#1,码风好看
543958
RLFEi楼主2022/8/17 17:08

rt

#include<bits/stdc++.h>
#define in rd()
#define int long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=1e4+10;
int T,n,w,h,x,y,l,ans,X[N<<1];
struct node{
	int l,r,h,val;
	node(){}
	node(int l,int r,int h,int val):l(l),r(r),h(h),val(val){}
	bool operator < (const node& res) const{return h==res.h ? val>res.val : h<res.h;}
}seg[N<<1];
struct segtree{
	int l,r,mx,tag;
	segtree(){}
	segtree(int l,int r,int mx,int tag):l(l),r(r),mx(mx),tag(tag){}
}tr[N<<3];
int rd()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
void build(int rt,int l,int r)
{
	tr[rt]=segtree(l,r,0,0);
	if(l==r) return;
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void pushdown(int rt)
{
	tr[ls].mx+=tr[rt].tag;
	tr[rs].mx+=tr[rt].tag;
	tr[ls].tag+=tr[rt].tag;
	tr[rs].tag+=tr[rt].tag;
	tr[rt].tag=0;
}
void update(int rt,int L,int R,int val)
{
	if(L<=tr[rt].l&&R>=tr[rt].r)
	{
		tr[rt].mx+=val;
		tr[rt].tag+=val;
		return;
	}
	pushdown(rt);
	int mid=(tr[rt].l+tr[rt].r)>>1;
	if(L<=mid) update(ls,L,R,val);
	if(R>mid) update(rs,L,R,val);
	tr[rt].mx=max(tr[ls].mx,tr[rs].mx);
}
signed main()
{
	T=in;
	while(T--)
	{
		n=in,w=in,h=in;
		memset(tr,0,sizeof(tr));
		for(int i=1;i<=n;++i)
		{
			x=in,y=in,l=in;
			seg[i]=node(x,x+w-1,y,l);
			seg[i+n]=node(x,x+w-1,y+h-1,-l);
			X[i]=x,X[i+n]=x+w-1;
		}
		n<<=1;
		sort(seg+1,seg+n+1);
		sort(X+1,X+n+1);
		int hc=unique(X+1,X+n+1)-X-1;
		build(1,1,hc);
		for(int i=1;i<=n;++i)
		{
			int l=lower_bound(X+1,X+hc+1,seg[i].l)-X;
			int r=lower_bound(X+1,X+hc+1,seg[i].r)-X;
			update(1,l,r,seg[i].val);
			ans=max(ans,tr[1].mx);
		}
		cout<<ans<<'\n';
	}
	return 0;
}
2022/8/17 17:08
加载中...