求助P1502的离散线段树做法
  • 板块学术版
  • 楼主hundunqidian
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/11 16:17
  • 上次更新2023/11/3 04:27:39
查看原帖
求助P1502的离散线段树做法
398310
hundunqidian楼主2023/8/11 16:17

求助

仅过第一个点…… 其余WA

#include<bits/stdc++.h>
#define int long long 
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
int const N=1e5+100;
struct Line{
	int x,y1,y2;
	int val; 
}; 
Line L[N]; 
bool cmp(Line a,Line b){
	if(a.x!=b.x) return a.x<b.x; //按x排序 
	if(a.val>0 && b.val>0) return a.val>b.val; //同正,则按val大到小排序 
	return a.val<b.val; //否则让删的在前(先删后增) 
}
struct Tree{
	int l,r,maxx; 
};
Tree t[N<<4]; 
int n,y[N],T; //y:矩形的y坐标 
int W,H,X,Y,val,ans;
void build(int rt,int l,int r){ //离散线段树建树 
	t[rt].l=y[l]; t[rt].r=y[r];
	t[rt].maxx=0; 
	if(l+1==r){ //叶子宽度为2时退出 
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(rt),l,mid);
	build(rs(rt),mid,r); //▲中间是重叠的 
	return ;
}
void pushup(int rt){
	t[rt].maxx=max(t[ls(rt)].maxx,t[rs(rt)].maxx);
	return ;
}
void change(int rt,int ul,int ur,int c){
	if(t[rt].l>=ur || t[rt].r<=ul) return ;
	if(ul<=t[rt].l && t[rt].r<=ur){
		t[rt].maxx+=c;
		//	pushup(rt);  //▲ 这里没有pushup,否则就都成0了 
		return ;
	}
	change(ls(rt),ul,ur,c);
	change(rs(rt),ul,ur,c);
	pushup(rt);
	return ;
}
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--){
		memset(L,0,sizeof(L));
		memset(t,0,sizeof(t));
		memset(y,0,sizeof(y));
		cin>>n>>W>>H;
		for(int i=1;i<=n;i++){
			cin>>X>>Y>>val;
			L[i]={X,Y,Y+H,val};
			L[n+i]={X+W,Y,Y+H,-val};
			y[i]=Y; y[n+i]=Y+H;
		}
		n=n<<1;
		sort(L+1,L+n+1,cmp);
		sort(y+1,y+n+1);
		build(1,1,n); 
		ans=0; //清空ans  
		for(int i=1;i<=n;i++){
			change(1,L[i].y1,L[i].y2,L[i].val);
			ans=max(ans,t[1].maxx);
		}
		cout<<ans<<endl;
	}
	return 0;
} 
2023/8/11 16:17
加载中...