P5490 【模板】扫描线 & 矩形面积并
题目描述
求 \(n\) 个四边平行于坐标轴的矩形的面积并。
输入格式
第一行一个正整数 \(n\)。
接下来 \(n\) 行每行四个非负整数 \(x_1, y_1, x_2, y_2\)，表示一个矩形的四个端点坐标为 \((x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)\)。
输出格式
一行一个正整数，表示 \(n\) 个矩形的并集覆盖的总面积。
输入输出样例 #1
输入 #1
2
100 100 200 200
150 150 250 255
输出 #1
18000
说明/提示
对于 \(20\%\) 的数据，\(1 \le n \le 1000\)。
对于 \(100\%\) 的数据，\(1 \le n \le {10}^5\)，\(0 \le x_1 < x_2 \le {10}^9\)，\(0 \le y_1 < y_2 \le {10}^9\)。
Updated on 4.10 by Dengduck（口胡） & yummy（实现）：增加了一组数据。
题解
首先我们按照 \(y\) 轴从小到大排序，那么每次我们要计算的区域面积就是$$S = len\times(y[i +1]- y[i])$$
类似这样，我们只需要关注x轴方向的并集长度就好了
![[Pasted image 20260101230420.png]]
我们发现 \(x\) 的范围非常大，所以我们对其离散化顺便去重
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end()); //对重复的 x 坐标去重
sort(line.begin(),line.end()); //对线段排序
为了方便，以下的区间全都是左闭右开
维护线段的并集，我们用 \(0\) 表示该点代表的区间没有被完全覆盖，反之就有
维护一个区间中被覆盖的点的数量，然后按 y 排序后循环线段，我们每次遇到一条横线，它可能是作为矩形的底边（这样子我们就要加入这条线上覆盖的点），也可能是顶边（这个矩形的影响到此结束，我们需要删去这条线），这是一个类似区间和，还要支持插入/删除线段，那么自然想到线段树
插入的时候，我们根据插入区间递归的往线段树对应的节点，修改其是否被完全覆盖，并计算该节点对应区间的并集长度是多少（len变量）
void update(int now)
{//被完全覆盖if(tree[now].cnt) tree[now].len = a[tree[now].r + 1] - a[tree[now].l];else{int lc = 2 * now,rc = 2 * now + 1;//当前已经是最小的区间了，但是没有cnt，所以整个区间没有被覆盖，所以是 0if(tree[now].l == tree[now].r) tree[now].len = 0;else tree[now].len = tree[lc].len + tree[rc].len; //不是最小区间，统合其左右子区间被覆盖区间的长度}
}
void build(int now,int l,int r)
{tree[now] = {l,r,0,0}; //构建线段树if(l == r) return ;int mid = (l + r) >> 1;build(2 * now,l,mid);build(2 * now + 1,mid + 1,r);
}
void modify(int now,int l,int r,int val)
{//如果修改区间完全包含了当前节点，那么标记当前节点为完全覆盖if(l <= tree[now].l && tree[now].r <= r){tree[now].cnt += val;update(now);return ;}int lc = 2 * now,rc = 2 * now + 1; //否则类似线段树递归更新左右节点if(l <= tree[lc].r) modify(lc,l,r,val);if(tree[rc].l <= r) modify(rc,l,r,val);update(now);
}
循环线段，每一次就有 \(high = y[i+1]-y[i]\)
至于如何处理删除的部分，我们在modify的时候传入 1 代表加入一条线段，-1 代表删除，这样就直接避免了使用懒标记这么麻烦的操作
接下来的处理就比较简单了，最需要注意的就是左闭右开，我们习惯的使用双闭区间在这种题目中会带来巨大的不便利，直接约定左闭右开就好了
//离散化之后 区间变成[x[0],x[1]),[x[1],x[2])ll ans = 0;for(int i = 0;i + 1 < line.size();++i){int high = line[i + 1].y - line[i].y;int left = lower_bound(a.begin(),a.end(),line[i].lx) - a.begin();int right = lower_bound(a.begin(),a.end(),line[i].rx) - a.begin();modify(1,left,right - 1,line[i].tag); //注意我们维护的区间全部都是左闭右开ans += 1ll * tree[1].len * high;//tree[1].len : 当前所有横轴线段的并集长度}cout << ans;
完整代码
#include<bits/stdc++.h>
// #define mod 998244353
// #define int long long //由于作者比较懒，所以直接使用这个了
using namespace std;
typedef long long ll;
typedef __int128 ix;
typedef long double ldb;
const ll V = 2e5 + 100;
const int INF = 1e9 + 7;
struct segment
{int lx,rx,y; //横线的左右端点和其 y 值int tag; //tag = 1 加入 , tag = -1 删除bool operator <(segment others) {return y < others.y; }
};
struct node //线段树的节点
{int l,r; //离散化之后该节点代表的区间的左右端点的x对应的下标，也就是这个[x[l],x[r + 1])int cnt; //cnt表示其被多少个矩形覆盖int len; //在当前所有覆盖之下，x 并的真实长度
};
vector<int> a;
vector<segment> line;
vector<node> tree(4 * V);
void update(int now)
{//被完全覆盖if(tree[now].cnt) tree[now].len = a[tree[now].r + 1] - a[tree[now].l];else{int lc = 2 * now,rc = 2 * now + 1;//当前已经是最小的区间了，但是没有cnt，所以整个区间没有被覆盖，所以是 0if(tree[now].l == tree[now].r) tree[now].len = 0;else tree[now].len = tree[lc].len + tree[rc].len; //不是最小区间，上传子区间被覆盖区间的长度}
}
void build(int now,int l,int r)
{tree[now] = {l,r,0,0};if(l == r) return ;int mid = (l + r) >> 1;build(2 * now,l,mid);build(2 * now + 1,mid + 1,r);
}
void modify(int now,int l,int r,int val)
{if(l <= tree[now].l && tree[now].r <= r){tree[now].cnt += val;update(now);return ;}int lc = 2 * now,rc = 2 * now + 1;if(l <= tree[lc].r) modify(lc,l,r,val);if(tree[rc].l <= r) modify(rc,l,r,val);update(now);
}
void solve()
{int n;cin >> n;int x1,x2,y1,y2;for(int i = 1;i <= n;++i){cin >> x1 >> y1 >> x2 >> y2;a.push_back(x1),a.push_back(x2);line.push_back({x1,x2,y1,1});line.push_back({x1,x2,y2,-1});}sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end()); //对重复的 x 坐标去重sort(line.begin(),line.end()); //对线段排序build(1,0,a.size() - 2); //0 ~ a.size() - 1 总共 a.size() - 2 个小区间//离散化之后 区间变成[x[0],x[1]),[x[1],x[2])ll ans = 0;for(int i = 0;i + 1 < line.size();++i){int high = line[i + 1].y - line[i].y;int left = lower_bound(a.begin(),a.end(),line[i].lx) - a.begin();int right = lower_bound(a.begin(),a.end(),line[i].rx) - a.begin();modify(1,left,right - 1,line[i].tag); //注意我们维护的区间全部都是左闭右开ans += 1ll * tree[1].len * high;//tree[1].len : 当前所有横轴线段的并集长度}cout << ans;}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);// int t;// cin >> t;// while(t--) solve();return 0;
}