对线段树部分的不解
查看原帖
对线段树部分的不解
125901
FxorG楼主2021/2/18 17:39

RT 这是我的代码 请问为什么在update时 不应该是update(rs,mid+1,r,cl,cr,x)吗 为什么mid不能加1

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

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

using namespace std; 

int y[N];
int n,tot;

struct tr {
	int sum,len;
	tr() {
		sum=len=0;
	}
}t[N<<2];

struct node {
	int h,l,r,fl;
	node() {
		h=l=r=fl=0;
	}
}g[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;
}

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

void push_up(int cur,int l,int r) {
	if(t[cur].sum>0) t[cur].len=y[r]-y[l];
	else t[cur].len=t[ls].len+t[rs].len;
}

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

signed main() {
	n=rd();
	int x1,y1,x2,y2;
	for(int i=1;i<=n;i++) {
		x1=rd(); y1=rd(); x2=rd(); y2=rd();
		g[(i<<1)-1].h=x1; g[(i<<1)-1].l=y1; g[(i<<1)-1].r=y2; g[(i<<1)-1].fl=1;
		g[i<<1].h=x2; g[i<<1].l=y1; g[i<<1].r=y2; g[i<<1].fl=-1;
		y[(i<<1)-1]=y1; y[i<<1]=y2;
	}
	n<<=1;
	sort(g+1,g+1+n,cmp); sort(y+1,y+1+n);
	for(int i=1;i<=n;i++) if(y[i]!=y[i+1]) y[++tot]=y[i];
	int ans=0;
	for(int i=1;i<n;i++) {
		update(1,1,n,g[i].l,g[i].r,g[i].fl);
		ans+=(g[i+1].h-g[i].h)*t[1].len;
		//cout<<t[1].len<<endl;
	}
	printf("%lld",ans);
	return 0;	
}
2021/2/18 17:39
加载中...