(玄关)蒟蒻橙题rand()%31+10分求条
查看原帖
(玄关)蒟蒻橙题rand()%31+10分求条
822439
lhz2022楼主2024/11/29 22:01

rt,扫描线和题解的方向是反的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() puts("I WILL AK")
#define N 100007
struct tree{
	int mx,lazy;
}tr[N<<2];
int T,n,w,h,tp;
int x[N],y[N],l[N],ck[N<<2];
inline int max(int a,int b){
	return a>b?a:b;
}
inline int min(int a,int b){
	return a<b?a:b;
}
inline void pushup(int rt){
	tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
}
inline void pushdown(int rt){
	int tg=tr[rt].lazy;
	tr[rt<<1].mx+=tg;
	tr[rt<<1].lazy+=tg;
	tr[rt<<1|1].mx+=tg;
	tr[rt<<1|1].lazy+=tg;
	tr[rt].lazy=0;
}
void upd(int rt,int l,int r,int ul,int ur,int k){
	if(ul<=l&&r<=ur){
		tr[rt].mx+=k;
		tr[rt].lazy+=k;
		return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(ul<=mid) upd(rt<<1,l,mid,ul,ur,k);
	if(ur>mid) upd(rt<<1|1,mid+1,r,ul,ur,k);
	pushup(rt);
}
int qry(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		return tr[rt].mx;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(qr<=mid) return qry(rt<<1,l,mid,ql,qr);
	else if(ql>mid) return qry(rt<<1|1,mid+1,r,ql,qr);
	else return max(qry(rt<<1,l,mid,ql,qr),qry(rt<<1|1,mid+1,r,ql,qr));
}
struct bl{
	int l,r,st,add;
	bool operator <(const bl &b) const{
		return st<b.st||(st==b.st&&add>b.add);
	}
}p[N<<2];
void clear(){
	for(int i=0;i<=n*4;++i){
		tr[i]={0,0};
		p[i]={0,0,0,0};
	}
	tp=0;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>T;
	while(T--){
		clear();
		cin>>n>>w>>h;
		for(int i=1;i<=n;++i){
			cin>>x[i]>>y[i]>>l[i];
			p[++tp]={x[i],x[i]+w-1,y[i],l[i]};
			p[++tp]={x[i],x[i]+w-1,y[i]+h-1,-l[i]};
			ck[tp-1]=p[tp].l;
			ck[tp]=p[tp].r;
		}
		//(int i=1;i<=tp;++i)	printf("i:%d l:%d,r:%d,st:%d,add:%d\n",i,p[i].l,p[i].r,p[i].st,p[i].add);
		sort(p+1,p+tp+1);
		sort(ck+1,ck+tp+1);
		int sum=unique(ck+1,ck+tp+1)-ck-1;
		for(int i=1;i<=tp;++i){
			p[i].l=lower_bound(ck+1,ck+sum+1,p[i].l)-ck;
			p[i].r=lower_bound(ck+1,ck+sum+1,p[i].r)-ck;
		}
		int ans=0;
		for(int i=1;i<=tp;++i){
			upd(1,1,sum,p[i].l,p[i].r,p[i].add);
			ans=max(ans,tr[1].mx);
			//cout<<p[i].st<<' '<<qry(1,1,tp,1,tp)<<'\n';
		}
		cout<<ans<<'\n';
	}
	return 0;
}
2024/11/29 22:01
加载中...