rt.
照着第一篇题解改过一遍,还是0pts。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
long long ans;
int X[200003],tot;
struct seg{
int l,r,y,f;
}sg[200003];
bool cmp(seg a,seg b){
return a.y<b.y;
}
struct segt{
int l,r,sum,len;
}a[800003];
void build(int id,int left,int right){
a[id].l=left,a[id].r=right;
a[id].sum=a[id].len=0;
if(left==right)
return;
int mid=(left+right)/2;
build(id*2,left,mid);
build(id*2+1,mid+1,right);
}
void pushup(int id){
if(a[id].sum)
a[id].len=X[a[id].r+1]-X[a[id].l];
else
a[id].len=a[id*2].len+a[id*2+1].len;
}
void add(int id,int left,int right,int k){
if(X[a[id].r+1]<=left || X[a[id].l]>=right)
return;
if(X[a[id].l]>=left && X[a[id].r+1]<=right){
a[id].sum+=k;
pushup(id);
return;
}
// if(X[a[id*2].r+1]>left)
add(id*2,left,right,k);
// if(X[a[id*2+1].l]<right)
add(id*2+1,left,right,k);
pushup(id);
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x_1,x_2,y_1,y_2;
scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
X[2*i-1]=x_1,X[2*i]=x_2;
sg[2*i-1]=seg{x_1,x_2,y_1,1};
sg[2*i]=seg{x_1,x_2,y_2,-1};
}
sort(sg+1,sg+2*n+1,cmp);
sort(X+1,X+2*n+1);
tot=unique(X+1,X+2*n+1)-X-1;
build(1,1,tot-1);
for(int i=1;i<2*n;i++){
add(1,sg[i].l,sg[i].r,sg[i].f);
ans+=1ll*a[1].len*(sg[i+1].y-sg[i].y);
}
printf("%d\n",ans);
return 0;
}