求助 关于维护线段树的区间
查看原帖
求助 关于维护线段树的区间
125901
FxorG楼主2021/2/19 13:53

RT 谢谢!

我90pts的代码 是维护线段的 而我在其他扫描线的题都是这种打法且都能过

也就是

// 维护mx值  即扫描线能覆盖到的最大值 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>

#define N (int)(1e5+5)
#define ls (cur<<1)
#define rs (ls|1)
#define int long long

using namespace std; 

int ny[N];
int n,w,h;

struct node {
	int h,l,r,fl;
}g[N];

struct tr {
	int sum,tag;
}t[N];

int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

void push_up(int cur) {
	t[cur].sum=max(t[ls].sum,t[rs].sum);
}

void push_down(int cur) {
	if(!t[cur].tag) return;
	t[ls].sum+=t[cur].tag; t[rs].sum+=t[cur].tag;
	t[ls].tag+=t[cur].tag; t[rs].tag+=t[cur].tag;
	t[cur].tag=0;
}

void update(int cur,int l,int r,int cl,int cr,int x) {
	if(ny[l]>=cr||ny[r]<=cl) return;
	if(cl<=ny[l]&&ny[r]<=cr) {
		t[cur].sum+=x;
		t[cur].tag+=x;
		return;
	}
	int mid=(l+r)>>1;
	push_down(cur);
	update(ls,l,mid,cl,cr,x);
	update(rs,mid,r,cl,cr,x);
	push_up(cur);
}

bool cmp(node x,node y) {
	return x.h==y.h?x.fl>y.fl:x.h<y.h;
}

signed main() {
	int tt=rd();
	while(tt--) {
		memset(g,0,sizeof(g));
		memset(ny,0,sizeof(ny));
		memset(t,0,sizeof(t));
		n=rd(); w=rd(); h=rd();
		int x,y,z;
		for(int i=1;i<=n;i++) {
			x=rd(); y=rd(); z=rd();
			g[(i<<1)-1]=node{x,y,y+h-1,z};
			g[i<<1]=node{x+w-1,y,y+h-1,-z};
			ny[(i<<1)-1]=y; ny[i<<1]=y+h-1;
		}
		n<<=1;
		sort(g+1,g+1+n,cmp);
		sort(ny+1,ny+1+n);
		int ans=0,tot=0;
		for(int i=1;i<=n;i++) if(ny[i]!=ny[i+1]) ny[++tot]=ny[i];
		for(int i=1;i<n;i++) {
			update(1,1,tot,g[i].l,g[i].r,g[i].fl);
			ans=max(ans,t[1].sum);
		}
		printf("%lld\n",ans);
	}	
}

但是在这道题 就似乎要维护2条线段之间 改成这样就过了 区别在update函数和调用update函数

// 维护mx值  即扫描线能覆盖到的最大值 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>

#define N (int)(1e6+5)
#define ls (cur<<1)
#define rs (ls|1)
#define int long long

using namespace std; 

int ny[N];
int n,w,h;

struct node {
	int h,l,r,fl;
}g[N];

struct tr {
	int sum,tag;
}t[N];

int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

void push_up(int cur) {
	t[cur].sum=max(t[ls].sum,t[rs].sum);
}

void push_down(int cur) {
	if(!t[cur].tag) return;
	t[ls].sum+=t[cur].tag; t[rs].sum+=t[cur].tag;
	t[ls].tag+=t[cur].tag; t[rs].tag+=t[cur].tag;
	t[cur].tag=0;
}

void update(int cur,int l,int r,int cl,int cr,int x) {
	if(ny[l]>cr||ny[r]<cl) return;
	if(cl<=ny[l]&&ny[r]<=cr) {
		t[cur].sum+=x;
		t[cur].tag+=x;
		return;
	}
	int mid=(l+r)>>1;
	push_down(cur);
	update(ls,l,mid,cl,cr,x);
	update(rs,mid+1,r,cl,cr,x);
	push_up(cur);
}

bool cmp(node x,node y) {
	return x.h==y.h?x.fl>y.fl:x.h<y.h;
}

signed main() {
	int tt=rd();
	while(tt--) {
		memset(g,0,sizeof(g));
		memset(ny,0,sizeof(ny));
		memset(t,0,sizeof(t));
		n=rd(); w=rd(); h=rd();
		int x,y,z;
		for(int i=1;i<=n;i++) {
			x=rd(); y=rd(); z=rd();
			g[(i<<1)-1]=node{x,y,y+h-1,z};
			g[i<<1]=node{x+w-1,y,y+h-1,-z};
			ny[(i<<1)-1]=y; ny[i<<1]=y+h-1;
		}
		n<<=1;
		sort(g+1,g+1+n,cmp);
		sort(ny+1,ny+1+n);
		int ans=0,tot=0;
		for(int i=1;i<=n;i++) if(ny[i]!=ny[i+1]) ny[++tot]=ny[i];
		for(int i=1;i<=n;i++) {
			update(1,1,tot-1,g[i].l,g[i].r,g[i].fl);
			ans=max(ans,t[1].sum);
		}
		printf("%lld\n",ans);
	}	
}
2021/2/19 13:53
加载中...