蒟蒻求助线段树裸题
查看原帖
蒟蒻求助线段树裸题
257621
翼德天尊楼主2020/8/2 10:56

调了快一上午了……求助各位大佬QwQ

对着题解改了改,但是改了半天还是不对。

评测记录

代码如下(加上了注释):

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 10005
int t_,n,wi,hi,q,lsh[MAXN<<1],tlsh;
struct node{//询问 
	int l,r,w,a;
	node(int l=0,int r=0,int w=0,int s=0)
		:l(l),r(r),w(w),a(s){}
}e[MAXN<<1];
struct node1{//线段树 
	int l,r,maxn,lz;
}t[MAXN<<3];
int read(){//快读 
	int w=0,f=1;
	char c=getchar();
	while (c>'9'||c<'0'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		w=(w<<3)+(w<<1)+(c^48);
		c=getchar();
	}
	return w*f;
}
bool cmp(node x_,node y_){//自定义排序 
	if (x_.w==y_.w) return x_.a>y_.a;
	return x_.w<y_.w;
}
void build(int i,int l,int r){//建树 
	t[i].l=l,t[i].r=r,t[i].maxn=t[i].lz=0;
	if (l==r){
		return;
	}
	int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r); 
}
void push_down(int i){//下传 
	if (t[i].lz){
		t[i<<1].lz+=t[i].lz;
		t[i<<1|1].lz+=t[i].lz;
		t[i<<1].maxn+=t[i].lz;
		t[i<<1|1].maxn+=t[i].lz;
		t[i].lz=0; 
	}
} 
void add(int i,int l,int r,int k){//扫描 
	if (t[i].l>=l&&t[i].r<=r){
		t[i].maxn+=k;
		t[i].lz+=k;
		return;
	}
	push_down(i);
	if (t[i<<1].r>=l) add(i<<1,l,r,k);
	if (t[i<<1|1].l<=r) add(i<<1|1,l,r,k);
	t[i].maxn=max(t[i<<1].maxn,t[i<<1|1].maxn);
}
int main(){
	t_=read();
	while (t_--){
		int ans=0;
		tlsh=q=0;
		n=read(),wi=read()-1,hi=read()-1;
		for (int i=1;i<=n;i++){
			int x=read(),y=read(),a=read();
			e[++q]=node(y,y+hi,x,a);
			e[++q]=node(y,y+hi,x+wi,-a);//处理询问 
			lsh[++tlsh]=y,lsh[++tlsh]=y+hi-1; 
		} 
		sort(lsh+1,lsh+1+tlsh);
		int g=unique(lsh+1,lsh+1+n)-lsh-1;//离散化 
		sort(e+1,e+1+q,cmp);//排序 
		build(1,1,n);
		for (int i=1;i<=q;i++){
			int l=lower_bound(lsh+1,lsh+1+g,e[i].l)-lsh;
			int r=lower_bound(lsh+1,lsh+1+g,e[i].r)-lsh;//离散化 
			add(1,l,r,e[i].a);
			ans=max(ans,t[1].maxn);
		}
		printf("%d\n",ans);
	}
	return 0;
}
2020/8/2 10:56
加载中...