10pts求调
查看原帖
10pts求调
1379742
Xiaohaoyu1020明天见_xj楼主2024/7/30 20:04

理论上没啥问题,只是理论,只能过样例

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
#define int long long
int xs[N<<1];
struct lin{
	int x1,x2,y,l;
} lines[N<<1];
struct node{
	int l,r;
	int x1,x2;
	int ma,add_tag;
}tre[N<<2];
#define self tre[p]
#define lp p<<1
#define rp p<<1|1
#define ls tre[lp]
#define rs tre[rp]
void push_up(int p){
	self.ma = max(ls.ma,rs.ma);
}
void push_down(int p){
	ls.add_tag += self.add_tag;
	rs.add_tag += self.add_tag;
	ls.ma += self.add_tag;
	rs.ma += self.add_tag;
	self.add_tag = 0;
}
void build(int p,int l,int r){
	self.l = l;
	self.r = r;
	self.x1 = xs[l];
	self.x2 = xs[r];
	self.ma = 0;
	self.add_tag =0;
	if(l == r){
		self.ma = 0;
		self.add_tag =0;
		return;
	}
	int mid = (l+r)/2;
	build(lp,l,mid);
	build(rp,mid+1,r);

	push_up(p);
}
void update(int p,int l,int r,int d){
	if(l>self.x2 || r < self.x1){
		return;
	}
	if(self.x1>= l && self.x2 <= r){
		self.add_tag += d;
		self.ma += d;
		return;
	}
	push_down(p);
	update(lp,l,r,d);
	update(rp,l,r,d);
	push_up(p);
}
int query(int p,int l,int r){
	if(l>self.r || r < self.l){
		return 0;
	}
	if(self.l>=l && self.r <=r){
		return self.ma;
	}
	push_down(p);
	return max(query(lp,l,r),query(rp,l,r));
}
int tot;
bool cmp(lin a,lin b){
	return a.y<b.y || (a.y == b.y && a.l>b.l);
}
void solve(){
	int n,W,H;
	cin>>n>>W>>H;
	for(int i= 1;i<=n;i++){
		int x,y,l;
		cin>>x>>y>>l;
		xs[i] = x;
		xs[i+n] = x+W-1;
		lines[i].x1 = x;
		lines[i].x2 = x+W-1;
		lines[i].y = y;
		lines[i].l = l;
		lines[i+n].x1 = x;
		lines[i+n].x2 = x+W-1;
		lines[i+n].y = y+H-1;
		lines[i+n].l = -l;
	}
	sort(xs+1,xs+1+n);
	tot = unique(xs+1,xs+1+n) - xs - 1;
	sort(lines+1,lines+1+n,cmp);
	build(1,1,tot);
	int ans = 0;
	for(lin l : lines){
		update(1,l.x1,l.x2,l.l);
		ans = max(ans,query(1,1,tot));
	}
	cout<<ans<<'\n';
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
}
2024/7/30 20:04
加载中...