代码求调
查看原帖
代码求调
759976
wflhx2011楼主2024/3/14 23:04
#include<bits/stdc++.h>
using namespace std;
double xbin[800005],ybin[800005],sum[800005]; 
long long add[800005],val[800005],xcnt,ycnt;
struct rect
{
	double xa,ya,xb,yb; 
}r[800005];
struct event
{
	long long xa,xb,v;
};
vector <event> g[800005];
inline void pushup(long long rt)
{
	if(val[rt<<1]==val[rt<<1|1])
	{
		val[rt]=val[rt<<1];
		sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	}
	else
	{
		long long f=(val[rt<<1]<val[rt<<1|1])?rt<<1:rt<<1|1;
		val[rt]=val[f];
		sum[rt]=sum[f];
	}
}
void build(long long l,long long r,long long root)
{
	val[root]=add[root]=0;
	if(l==r)
	{
		sum[root]=xbin[l]-xbin[l-1];
		return ;
	}
	long long mid=(l+r)>>1;
	build(l,mid,root<<1);
	build(mid+1,r,root<<1|1);
	pushup(root);
}
inline void pushdown(long long root,long long len)
{
	if(add[root])
	{
		val[root<<1]+=add[root];
		val[root<<1|1]+=add[root];
		add[root<<1]+=add[root];
		add[root<<1|1]+=add[root];
		add[root]=0;
	}
}
void update(long long L,long long R,long long c,long long l,long long r,long long root)
{
	if(L<=l&&r<=R)
	{
		add[root]+=c;
		val[root]+=c;
		return ;
	}
	pushdown(root,r-l+1);
	long long mid=(l+r)>>1;
	if(L<=mid)
		update(L,R,c,l,mid,root<<1);
	if(mid+1<=R)
		update(L,R,c,mid+1,r,root<<1|1);
	pushup(root);
}
int main()
{
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		cin>>r[i].xa>>r[i].ya>>r[i].xb>>r[i].yb;
		xbin[++xcnt]=r[i].xa;
		xbin[++xcnt]=r[i].xb;
		ybin[++ycnt]=r[i].ya;
		ybin[++ycnt]=r[i].yb;
	}
	sort(xbin+1,xbin+xcnt+1);
	sort(ybin+1,ybin+ycnt+1);
	xcnt=unique(xbin+1,xbin+xcnt+1)-xbin-1;
	ycnt=unique(ybin+1,ybin+ycnt+1)-ybin-1;
	for(long long i=1;i<=n;i++)
	{
		long long xp=lower_bound(xbin+1,xbin+xcnt+1,r[i].xa)-xbin;
		long long xq=lower_bound(xbin+1,xbin+xcnt+1,r[i].xb)-xbin;
		long long yp=lower_bound(ybin+1,ybin+ycnt+1,r[i].ya)-ybin;
		long long yq=lower_bound(ybin+1,ybin+ycnt+1,r[i].yb)-ybin;
		if(xp<xq)
		{
			g[yp].push_back((event){xp+1,xq,1});
			g[yq].push_back((event){xp+1,xq,-1});
		}
	}
	xbin[0]=xbin[1];
	ybin[0]=ybin[1];
	build(1,xcnt,1);
	double ans=0;
	for(long long i=1;i<=ycnt;i++)
	{
		double tmp=sum[1];	
		if(val[1]>0)
			tmp=0;
		ans+=(ybin[i]-ybin[i-1])*(xbin[xcnt]-xbin[1]-tmp);
		for(long long j=0;j<g[i].size();j++)
			update(g[i][j].xa,g[i][j].xb,g[i][j].v,1,xcnt,1);
	}	
	cout<<(long long)(ans);
	return 0;
}
2024/3/14 23:04
加载中...