AcWing 247. 亚特兰蒂斯 的简化版:
之前写过关于扫描线 + 线段树问题的分析题解:
cpp 扫描线 + 线段树
// 扫描线 + 线段树
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
struct Seg{
int x,y1,y2;
int k;
bool operator< (const Seg &t)const{
return x<t.x;
}
}seg[N<<1];
struct {
int l,r;
int cnt;// cover属性 当前区段(整段)被有效覆盖次数
int len;// 当前区间内的有效长度
}tr[N<<2];
inline void pushup(int u){
if(tr[u].cnt > 0 ) tr[u].len = tr[u].r - tr[u].l + 1;
else if(tr[u].cnt == 0 && tr[u].l == tr[u].r) tr[u].len = 0;
else tr[u].len = tr[u<<1].len + tr[u<<1|1].len;
}
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);
}
inline void modify(int u,int l,int r,int k){
if(tr[u].l>=l && tr[u].r<=r) {
tr[u].cnt += k;
pushup(u);
}
else{
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.tie(0)->sync_with_stdio(false);
int n;
cin>>n;
int m = 0;
while(n--){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
seg[m++] = {x1,y1,y2,1};
seg[m++] = {x2,y1,y2,-1};
}
sort(seg,seg+m);
build(1,0,10000);
int res = 0;
for(int i=0;i<m;i++){
// tr[1].len是当前y轴实际使用长度, 乘上x就是面积
if(i>0)res += tr[1].len*(seg[i].x - seg[i-1].x);
modify(1,seg[i].y1,seg[i].y2-1,seg[i].k);
}
cout<<res<<endl;
return 0;
}