求求大神救救孩子!!!Orz Orz 20分样例过了·
查看原帖
求求大神救救孩子!!!Orz Orz 20分样例过了·
539342
Vuglar_zuo楼主2023/8/8 20:12
#include<bits/stdc++.h>
using namespace std;
struct data
{
	long long x;
	long long yy1;
	long long yy2;
	long long f;
}q[205000];
long long total[205000];
struct dd
{
	long long l;
	long long r;
	long long m;
	long long ans;
}p[805000];
bool cmp1(data a,data b)
{
	return a.x<b.x;
}
void build(long long l,long long r,long long id)
{
	p[id].l=l;
	p[id].r=r;
	if(l==r)
	{
		return;
	}
	long long m=(l+r)/2;
	build(l,m,id*2);
	build(m+1,r,id*2+1);
}
void updatetree(long long l,long long r,long long id,long long f)
{
	if(l<=p[id].l&&p[id].r<=r)
	{
		p[id].m+=f;
		if(p[id].m>0)
		{
			p[id].ans=total[p[id].r+1]-total[p[id].l];
		}
		else
		{
			p[id].ans=p[id*2].ans+p[id*2+1].ans;
		}
		return ;
	}
	long long m=(p[id].l+p[id].r)/2;
	if(l<=m)
	{
		updatetree(l,r,id*2,f);
	}
	if(r>m)
	{
		updatetree(l,r,id*2+1,f);
	}
	if(p[id].m>0)
	{
		p[id].ans=total[p[id].r+1]-total[p[id].l];
	}
	else
	{
		p[id].ans=p[id*2].ans+p[id*2+1].ans;
	}
}
int main()
{
	long long n,m;
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
	{
		long long a,b,j,d;
		scanf("%lld%lld%lld%lld",&a,&b,&j,&d);
		q[i]={a,b,d,1};
		q[i+n]={j,b,d,-1};
		total[i]=b;
		total[i+n]=d;
	}
	sort(total+1,total+1+2*n);
	long long j=2;
	for(long long i=2;i<=2*n;i++)
	{
		if(total[i-1]!=total[i])
		{
			total[j]=total[i];
			j++;
		}
	}
	for(long long i=1;i<=2*n;i++)
	{
		q[i].yy1=lower_bound(total+1,total+j,q[i].yy1)-total;
		q[i].yy2=lower_bound(total+1,total+j,q[i].yy2)-total;
	}
	sort(q+1,q+1+2*n,cmp1);
	build(1,j-1,1);
	long long ans=0;
	for(long long i=1;i<2*n;i++)
	{
		updatetree(q[i].yy1,q[i].yy2-1,1,q[i].f);
		ans+=1LL*(q[i+1].x-q[i].x)*p[1].ans;
	}
	printf("%lld",ans);
	return 0;
}
2023/8/8 20:12
加载中...