代码奉上:
#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
using namespace std;
const int N=1e5+6;
int n,m,num;
struct P{
double x,y,z;
int k;
inline bool operator < (const P &o) const{
return x<o.x;
}
}a[N<<1];
double raw[N<<1];
map<double,int> val;
struct T{
int l,r,cnt;
double len;
}t[N<<3];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r,t[p].cnt=0,t[p].len=0;
if(l==r) return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void change(int p,int l,int r,double k){
if(l<=t[p].l&&r>=t[p].r){
t[p].len=((t[p].cnt+=k)?raw[t[p].r+1]-raw[t[p].l]:(t[p].l==t[p].r?0:t[ls].len+t[rs].len));
return;
}//段加一是点 ↑ 断了 单点长度为零 子区间的覆盖长度值
if(l<=mid) change(ls,l,r,k);
if(r>mid) change(rs,l,r,k);
t[p].len=(t[p].cnt?raw[t[p].r+1]-raw[t[p].l]:t[ls].len+t[rs].len);
// 全不全? 不全就整个区间 断了就左子区间加右子区间 ****ooo******
// *************
return;
}
inline void Atlantis(){
for(int i=1;i<=n;i++){
int k=i<<1;//第i对
double y,z;//y1,y2;
scanf("%lf%lf%lf%lf",&a[k-1].x,&y,&a[k].x,&z);//四元组
raw[k-1]=a[k-1].y=a[k].y=y;
raw[k]=a[k-1].z=a[k].z=z;
a[k-1].k=1,a[k].k=-1;
}
n<<=1;//n个矩形,2n个坐标
sort(raw+1,raw+n+1);//按x排序
int m=unique(raw+1,raw+n+1)-raw-1;//去重后的个数
for(int i=1;i<=m;i++){
val[raw[i]]=i;//建立映射关系
}
sort(a+1,a+n+1);//四元组按x排序
build(1,1,m-1);//m个点,m-1个区间
double ans=0;//面积
for(int i=1;i<n;i++){//共2n-1个区间
int y=val[a[i].y];//y1对应离散值
int z=val[a[i].z]-1;//y2对应离散值
change(1,y,z,a[i].k);
ans+=t[1].len*(a[i+1].x-a[i].x);//加上
}//扫过的面积
printf("%.0lf\n",ans);
}
int main(){
// freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
while(cin>>n&&n) Atlantis();
return 0;
}
大佬们有时间的话帮忙查下错,没时间就算了QwQ