题目描述
我们给出了一个(轴对齐的)矩形列表 rectangles
。 对于 rectangle[i] = [x1, y1, x2, y2]
,其中 (x1,y1)
是矩形 i
左下角的坐标,(x2,y2)
是该矩形右上角的坐标。
找出平面中所有矩形叠加覆盖后的总面积。由于答案可能太大,请返回它对 10 ^ 9 + 7 取模的结果。
样例
输入:[[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出:6
解释:如图所示。
输入:[[0,0,1000000000,1000000000]]
输出:49
解释:答案是 10^18 对 (10^9 + 7) 取模的结果, 即 (10^9)^2 = (-7)^2 = 49。
说明
1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= rectangles[i][j] <= 10^9
- 矩形叠加覆盖后的总面积不会超越
2^63 - 1
,这意味着可以用一个 64 位有符号整数来保存面积结果。
算法
(离散化,扫描线,线段树) $O(n \log n)$
- 我们分别用一个数组,去离散化纵坐标的点的范围。
- 存储所有的竖线四元组
(x, y1, y2, d)
:如果某个竖线是某个矩形左侧的竖线,则记录它的权值d
为 +1,否则为 -1。 - 对所有竖线按照横坐标从小到大排序。维护一个在 y 轴上的线段树,记录 y 轴上竖线覆盖后的总长度。
- 从最小的坐标开始扫描所有横坐标,对于每个横坐标,首先计算当前 y 轴上的覆盖总长度与上一个横坐标距离的乘积,然后在线段树上更新竖线(添加或者删除)。
- 我们用
sz
数组来存储线段树上每个结点的覆盖长度,tag
用来记录结点是否被完全覆盖的标记。因为每个竖线都是添加一次,删除一次,且不会出现标记为负的情况,询问也是对整体区间的询问。所以我们可以将标记永久化,不用(也不能)下放标记。 - 所以更新线段树的时候,如果结点的
tag
为 0,则sz
从左右子结点sz
更新。否则sz
为当前结点的区间长度。 - 注意线段树记录的是区间,不是点(区间范围为 1 到 yn - 1)。
时间复杂度
- 排序离散化的时间复杂度为 $O(n \log n)$,扫描线移动 $O(n)$ 次,每次更新的时间复杂度为 $O(\log n)$。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要额外的离散化数组和线段树结点存储空间,故空间复杂度为 $O(n)$。
C++ 代码
struct Tuple {
int x, y1, y2, d;
Tuple(int x_, int y1_, int y2_, int d_): x(x_), y1(y1_), y2(y2_), d(d_) {}
bool operator < (const Tuple& other) const {
return x < other.x;
}
};
class Solution {
public:
vector<int> sz, tag;
vector<int> yc;
void pushup(int l, int r, int rt) {
if (tag[rt] == 0) {
if (l < r)
sz[rt] = sz[rt << 1] + sz[rt << 1 | 1];
else
sz[rt] = 0;
} else {
sz[rt] = yc[r] - yc[l - 1];
}
}
void update(int L, int R, int c, int l, int r, int rt) {
if (L <= l && r <= R) {
tag[rt] += c;
pushup(l, r, rt);
return;
}
int mid = (l + r) >> 1;
if (L <= mid)
update(L, R, c, l, mid, rt << 1);
if (mid < R)
update(L, R, c, mid + 1, r, rt << 1 | 1);
pushup(l, r, rt);
}
int rectangleArea(vector<vector<int>>& rectangles) {
const int mod = 1000000007;
int n = rectangles.size();
for (int i = 0; i < n; i++) {
yc.push_back(rectangles[i][1]);
yc.push_back(rectangles[i][3]);
}
sort(yc.begin(), yc.end());
int yn = unique(yc.begin(), yc.end()) - yc.begin();
yc.resize(yn);
vector<Tuple> line;
for (int i = 0; i < n; i++) {
int x1 = rectangles[i][0], y1 = rectangles[i][1];
int x2 = rectangles[i][2], y2 = rectangles[i][3];
y1 = lower_bound(yc.begin(), yc.end(), y1) - yc.begin();
y2 = lower_bound(yc.begin(), yc.end(), y2) - yc.begin();
line.emplace_back(x1, y1, y2, 1);
line.emplace_back(x2, y1, y2, -1);
}
sort(line.begin(), line.end());
sz.resize(yn << 2, 0);
tag.resize(yn << 2, 0);
int ans = 0, last_x = -1;
for (int i = 0; i < 2 * n; i++) {
if (i > 0)
ans = (ans + (long long)(line[i].x - last_x) * sz[1]) % mod;
last_x = line[i].x;
while (1) {
update(line[i].y1 + 1, line[i].y2, line[i].d, 1, yn - 1, 1);
if (i == 2 * n - 1 || line[i + 1].x != line[i].x)
break;
i++;
}
}
return ans;
}
};