刚刚自学完扫描线,连挂三发心态炸了
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
ll n,temp=1,lazy[maxn<<3],ans;
ll X1,X2,Y1,Y2;
double s[maxn<<3];
double min(double x, ll y) {
return x<y?x:y;
}
double max(double x, ll y) {
return x>y?x:y;
}
struct Node1{
double l,r;
double sum;
} t[maxn<<3];
struct Node2{
double x,y1,y2;
ll flag;
} p[maxn<<3];
bool cmp(Node2 a, Node2 b) {
return a.x < b.x;
}
void pushup(ll rt) {
if(lazy[rt]>0) {
t[rt].sum=t[rt].r-t[rt].l;
}
else {
t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
}
}
void build(ll rt, ll l, ll r) {
if(r-l>1) {
t[rt].l=s[l];
t[rt].r=s[r];
build(rt*2,l,(l+r)/2);
build(rt*2|1,(l+r)/2,r);
pushup(rt);
}
else {
t[rt].l=s[l];
t[rt].r=s[r];
t[rt].sum=0;
}
return;
}
void update(ll rt, ll y1, ll y2, ll flag) {
if(t[rt].l==y1 && t[rt].r==y2) {
lazy[rt]+=flag;
pushup(rt);
return;
} else{
if(t[rt*2].r>y1) {
update(rt*2,y1,min(t[rt*2].r,y2),flag);
}
if(t[rt*2+1].l<y2) {
update(rt*2|1,max(t[rt*2+1].l,y1),y2,flag);
}
pushup(rt);
}
}
int main() {
cin>>n;
ans=0;
for(int i=0;i<n;i++) {
cin>>X1>>Y1>>X2>>Y2;
p[i].x=X1;
p[i].y1=Y1;
p[i].y2=Y2;
p[i].flag=1;
p[i+n].x=X2;
p[i+n].y1=Y1;
p[i+n].y2=Y2;
p[i+n].flag=-1;
s[i+1]=Y1;
s[i+n+1]=Y2;
}
sort(s+1,s+(2*n+1));
sort(p,p+2*n,cmp);
build(1,1,2*n);
memset(lazy,0,sizeof(lazy));
update(1,p[0].y1,p[0].y2,p[0].flag);
for(int i=1;i<2*n;i++) {
ans+=(p[i].x-p[i-1].x)*t[1].sum;
update(1,p[i].y1,p[i].y2,p[i].flag);
}
cout<<ans<<endl;
return 0;
}