【模板】 扫描线 & 矩形面积并

#线段树 #数据结构

题目描述

求 $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$。

思路

扫描线模板题，使用线段树维护长度，然后枚举两条扫描线之间的距离，即可维护面积并了。

代码

const int N = 2e5 + 10;struct line {int x1, x2, y;int tag; // 1/0 入边出边bool operator<(const line& l) const {return y < l.y;}
}L[N];#define ls(x) x<< 1 
#define rs(x) x<< 1 | 1  struct node {int l, r, cnt, len;
}tree[N * 8];int X[N];void build(int p,int l,int r) {tree[p] = { l,r,0,0 };if (l == r) {return;}int mid = l + r >> 1;build(ls(p),l, mid );build(rs(p),mid+1, r );
}void push_up(int p) {int l = tree[p].l, r = tree[p].r;if (tree[p].cnt) tree[p].len = X[r + 1] - X[l];else {tree[p].len = tree[ls(p)].len + tree[rs(p)].len;}
}void update(int p , int x, int y,int tag) {if (x <= tree[p].l && y >= tree[p].r) {tree[p].cnt += tag;push_up(p);return;}int mid = tree[p].l + tree[p].r >> 1;if (y <= mid) {update(ls(p), x, y, tag);}else if (x>=mid +1) {update(rs(p), x, y, tag);}else {update(ls(p), x, y, tag);update(rs(p), x, y, tag);}push_up(p);
}void solve() {int n;std::cin >> n;for (int i = 1; i <= n; ++i) {int x1, y1, x2, y2;std::cin >> x1 >> y1 >> x2 >> y2;X[i] = x1; X[i + n] = x2;L[i] = { x1,x2,y1,1 }; L[i + n] = { x1,x2,y2,-1 };}n <<= 1;std::sort(X + 1, X + 1 + n);std::sort(L + 1, L + 1 + n);int m = std::unique(X + 1, X + 1 + n) - X - 1;build(1, 1, m - 1);ll res = 0;for (int i = 1; i <= n - 1; ++i) {int l = std::lower_bound(X + 1, X + m + 1, L[i].x1) - X;int r = std::lower_bound(X + 1, X + m + 1, L[i].x2) - X;update(1, l, r - 1, L[i].tag);res += (ll)tree[1].len * (L[i + 1].y - L[i].y);}std::cout << res << "\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}return 0;
}