代码求条
查看原帖
代码求条
759976
wflhx2011楼主2025/1/12 15:37
#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,cover[16000005];
double xa,xb,ya,yb,x[2000005],len[16000005];
struct nod
{
	double l,r,h;
	int mark;
    nod(double ll=0,double rr=0,double hh=0,int ff=0):l(ll),r(rr),h(hh),mark(ff) {}
    bool operator<(nod a) 
	{ 
		return h<a.h; 
	}
}line[2000005];
void build(int l,int r,int rt)
{
	cover[rt]=0;
	len[rt]=0;
	if(l==r)
		return ;
	int mid=(l+r)/2;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
}
void pushup(int l,int r,int rt)
{
	if(cover[rt])
		len[rt]=x[r+1]-x[l];
	else if(l==r)
		len[rt]=0;
	else
		len[rt]=len[rt<<1]+len[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		cover[rt]+=c;
		pushup(l,r,rt);
		return ;
	}
	if(L>r||l>R)
		return ;
	int mid=(l+r)/2;
	update(L,R,c,l,mid,rt<<1);
	update(L,R,c,mid+1,r,rt<<1|1);
	pushup(l,r,rt);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>xa>>ya>>xb>>yb;
		line[cnt]={xa,xb,ya,1};
		x[cnt++]=xa;
		line[cnt]={xa,xb,yb,-1};
		x[cnt++]=xb;
	}	
	sort(line,line+cnt);
	sort(x,x+cnt); 
	int m=unique(x,x+cnt)-x;
	build(0,m-1,1);
	long long ans=0;
	int l,r;
	for(int i=0;i<cnt;i++)
	{
		l=lower_bound(x,x+m,line[i].l)-x;
		r=lower_bound(x,x+m,line[i].r)-x-1;
		update(l,r,line[i].mark,0,m-1,1);
		ans+=(line[i+1].h-line[i].h)*len[1];
	}	
	cout<<ans<<endl;
	return 0;
}
2025/1/12 15:37
加载中...