#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n;
vector<ll> place;
struct Range{
int x,y1,y2,k;
bool operator <(const Range &t) const{
return x<t.x;
}
}range[N];
int cnt;
struct Node{
int l,r;
int len;
int cnt;
}tr[N*4];
int find(int x)
{
return lower_bound(place.begin(),place.end(),x)-place.begin();
}
void pushup(int u)
{
if(tr[u].cnt) tr[u].len=place[tr[u].r+1]-place[tr[u].l];
else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
else tr[u].len=0;
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r) return;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void modify(int u,int l,int r,int k)
{
if(l<=tr[u].l&&tr[u].r<=r){
tr[u].cnt+=k;
pushup(u);
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
int main()
{
cin>>n;
while(n--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
range[++cnt]={x1,y1,y2,1},range[++cnt]={x2,y1,y2,-1};
place.push_back(y1),place.push_back(y2);
}
sort(place.begin(),place.end());
place.erase(unique(place.begin(),place.end()),place.end());
sort(range+1,range+1+cnt);
build(1,0,place.size()-2);
ll ans=0;
for(int i=1;i<=cnt;i++){
if(i>1) ans+=(ll)tr[1].len*(range[i].x-range[i-1].x);
modify(1,find(range[i].y1),find(range[i].y2)-1,range[i].k);
}
printf("%lld\n",ans);
return 0;
}
我没买进阶课,这个题现在我只能看到题解看不到题我去
可以稍微加一点注释,更好理解