题目介绍
原题链接: 2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) F-Rectangle
给出n个与坐标轴对齐的矩形，求被奇数个矩形所覆盖的面积。
输入格式：一个n，然后n行，每行4个数字(x_1, y_1, x_2, y_2)分别表示这个矩形的左下角和右上角坐标。坐标范围[0,1e9] 类型int。
经典的扫描线算法可以看这个up的视频，讲的特别好。
思路
- 扫描线板子题，需要稍微做一些调整。
- 这里还是先介绍一下经典的扫描线算法。
经典的扫描线问题是求覆盖面积。模拟一根从左到右扫描的线段，这条线段每碰到一段矩形的边界，就更新一次自己的长度。碰到左边界则加相应长度，有边界则减。这里要注意重叠的部分不要计入。这种区间修改的操作一般可以用线段树实现。每次更新长度前，将当前长度与上一次更新至今的距离(Delta x)相乘，就得出了一个区间的面积。所有区间面积加起来即是答案。- 在这道题中，要求的是“被覆盖了奇数个矩形的面积”。所以需要作出一些调整。容易观察到，奇偶这一性质是互相转变的，线段经过左边界和右边界，都一样是改变了某段区域被覆盖次数的奇偶性。因此我们对一般的线段树进行以下调整：
- 维护一个cover数组，表示区间内值为1的线段总长度。
- 修改其实就是把区间内的线段覆盖奇偶性倒换，容易知道：进行一次更新操作后，区间的cover数就变成len-cover。
- lazy标记初始化为0，每次完全更新一个区间，就将lazy^=1，这是因为对同一个区间“翻转”两次，操作会相互抵消。当向下递归时，当前lazy标记为1就说明有还未抵消的“翻转”操作，需要向下传递。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,m,rt<<1
#define rson m,r,(rt<<1)|1
const int maxn=1e5+10;
int n,tot;
struct node{
ll x,low,high;
bool operator<(const node& tmp)const{
return x<tmp.x;
}
};
node nd[maxn<<1];
int y[maxn<<1];//记录所有y坐标，用于离散化
ll cover[maxn*12];//正常应该是8倍，这里因为采用点作为线段树结点，
//右区间不用m+1,所以需要多出1/2的空间。
bool lz[maxn*12];//表示是否需要down
void pushDown(int rt,int l,int r){
if(l==r) return;
if(!lz[rt]) return;
int ls=rt<<1,rs=rt<<1|1;
int m=(l+r)>>1;
cover[ls]=y[m]-y[l]-cover[ls];
cover[rs]=y[r]-y[m]-cover[rs];
lz[ls]^=1;
lz[rs]^=1;
lz[rt]^=1;
}
void pushUp(int rt){
cover[rt]=cover[rt<<1]+cover[rt<<1|1];
}
void update(int L,int R,int l=1,int r=tot,int rt=1){
if(l==r) return ;
if(L<=y[l] && y[r]<=R){
cover[rt]=y[r]-y[l]-cover[rt];
lz[rt]^=1;
pushDown(rt,l,r);
return;
}
if(l==r-1) return;//一个小区间，不全覆盖就无意义，防止无限递归
int m=(l+r)>>1;
if(R>=y[l]){
pushDown(rt,l,r);
update(L,R,lson);
}
if(L<=y[r]){
pushDown(rt,l,r);
update(L,R,rson);
}
pushUp(rt);
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
ll a,b,c,d;
for(int i=1;i<=n;++i){
cin>>a>>b>>c>>d;
nd[i].x=a,nd[i].high=d,nd[i].low=b;
nd[n+i].x=c,nd[n+i].high=d,nd[n+i].low=b;
y[i]=b,y[n+i]=d;
}
sort(nd+1,nd+2*n+1);
// 离散化
sort(y+1,y+2*n+1);
tot=unique(y+1,y+2*n+1)-y-1;
ll ans=0;
nd[0].x=nd[1].x;
for(int i=1;i<=n*2;++i){
ans+=(nd[i].x-nd[i-1].x)*cover[1];
if(nd[i].high>nd[i].low)
update(nd[i].low,nd[i].high);
}
ans+=(nd[n*2].x-nd[n*2-1].x)*cover[1];
cout<<ans<<'
';
return 0;
}