感到焦虑,恐慌,迷茫,……呜
不知道你们怎么样
顺便帮个同学求助扫描线
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long n,ans=0;
long long p[200003],lp=0,l,lq=0;
long long x1,y1,x2,y2;
struct XXX{long long y,val,lx,rx;}q[200003];
long long f[800003],len[800003];
bool cmp(struct XXX u,struct XXX v){return u.y<v.y;}
void upd(int w,int l,int r)
{
if(f[w])
len[w]=p[r+1]-p[l];
else
len[w]=len[w*2]+len[w*2+1];
}
void add(int w,int l,int r,int u,int v,int k)
{
if(p[r+1]<= u || v<=p[l])
return;
if(u<=p[l] && p[r+1]<=v)
{
f[w]+=k;
upd(w,l,r);
return;
}
int mid=(l+r)/2;
add(w*2,l,mid,u,v,k);
add(w*2+1,mid+1,r,u,v,k);
upd(w,l,r);
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
p[++lp]=x1;p[++lp]=x2;
q[++lq]=(struct XXX){y1,1,x1,x2};
q[++lq]=(struct XXX){y2,-1,x1,x2};
}
sort(p+1,p+lp+1);
l=unique(p+1,p+lp+1)-p-1;
sort(q+1,q+lq+1,cmp);
for(int i=1;i<lq;i++)
{
add(1,1,l-1,q[i].lx,q[i].rx,q[i].val);
ans+=(q[i+1].y-q[i].y)*len[1];
}
printf("%lld",ans);
return 0;
}