求调
查看原帖
求调
1248522
mlvx楼主2024/5/21 17:11
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pl (p<<1)
#define pr (p<<1|1)
const int N=1e6+10;
struct line{int xl,xr,y,qz;}L[N<<1];bool operator<(line a,line b){return a.y<b.y;}
struct Tree{int cnt;ll len;}tr[N<<2];
int n,xl,yl,xr,yr,x[N<<1];ll ans;
void push_up(int l,int r,int p){tr[p].len=(tr[p].cnt?x[r+1]-x[l]:tr[pl].len+tr[pr].len);}
void update(int l,int r,int le,int ri,int v,int p){
	if(x[r+1]<=le||x[l]>=ri)return;
	if(x[l]>=le&&x[r+1]<=ri)return tr[p].cnt+=v,push_up(l,r,p);
	int mid=l+r>>1;
	update(l,mid,le,ri,v,pl),update(mid+1,r,le,ri,v,pr),push_up(l,r,p);
}int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>xl>>yl>>xr>>yr,x[2*i-1]=xl,x[2*i]=xr,L[2*i-1]={xl,xr,yl,1},L[2*i]={xl,xr,yr,-1};
	n<<=1,sort(x+1,x+n+1),sort(L+1,L+n+1),n=unique(x+1,x+n+1)-x-1;
	for(int i=1;i<n;i++)update(1,n-1,L[i].xl,L[i].xr,L[i].qz,1),ans+=tr[1].len*(L[i+1].y-L[i].y);
	return cout<<ans,0;
}
2024/5/21 17:11
加载中...