自动搬运

查看原文

来自洛谷，原作者为

	Ofnoname 亡者归来

搬运于2025-08-24 21:31:28，当前版本为作者最后更新于2019-10-26 15:42:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

扫描线板子题，可以去搜博客看一下。这里搬运一下以前口胡的。

首先将y坐标离散化，但是要保留原坐标。

我们用一根竖直的线从左向右依次扫描，每当与矩形的竖直边重合时就累加一次面积，相当于把并集图形分割为一个一个小的矩形。

具体来说，建立数组$d[i]$保存这个y坐标被覆盖了多少次，并把矩形的竖边按$(x,y1,y2,d)$表示，d表示这是矩形的左边界(1)还是右边界(-1)，比如图中第一条边就是$(2,3,7,1)$，并按x排序依次考虑。

对所有竖线先按x排序，有些写法里对竖线排序时如果x相等会按c排序，但是容易发现这是毫无影响的。

对于每条边，我们把$[y1,y2)$的值都加上d，表示这条左数边把y轴这些地方又覆盖了一次，或者右数边表示该矩形对y轴影响已经结束。

（为什么是左闭右开：我们把点转化为线段来求覆盖次数，点的数量是比线段的数量多1个的，比如第一条线段里$[3,7]$是有5个点的，但是放在d数组里只有4个值需要修改。）

接着统计答案，下一个矩形的宽就是相邻两根竖边的x坐标差，而长度就是d数组里至少被覆盖一次的坐标数。

（图中：$2*4+2*6+1*8+2*7+1*7+1*4+3*4+0*0\ =\ 60$）

d数组涉及了区间修改和区间查询，可以使用线段树来维护。

由于只需要查询$(1,N)$里的覆盖次数，我们的懒标记可以不用下推。更新时，如果一个节点有懒标记（表示自己被完全覆盖的次数），那么他的贡献就是区间总长度（因为被覆盖），否则递归计算左右儿子并相加。

#include <bits/stdc++.h>
#define MAX (2000 + 7)
using namespace std;

struct Node { int x, y0, y1, c; } a[MAX];
int cmp(Node a, Node b) { return a.x < b.x; }

unordered_map <int, int> H;

int N, M, qy[MAX];
long long ans;

struct Segtree
{
	#define i0 (i << 1)
	#define i1 (i << 1 | 1)
	int L[MAX << 2], R[MAX << 2], v[MAX << 2], len[MAX << 2];
	void init(int i, int l, int r)
	{
		L[i] = l, R[i] = r, v[i] = len[i] = 0;
		if (l != r) {
			int mid = l + r >> 1;
			init(i0, l, mid), init(i1, mid+1, r);
		}
	}
	void add(int i, int l, int r, int c)
	{
		if (r < L[i] || R[i] < l) return;
		if (l <= L[i] && R[i] <= r)
			v[i] += c;
		else add(i0, l, r, c), add(i1, l, r, c);
		if (v[i]) len[i] = qy[R[i]+1] - qy[L[i]];//完全覆盖时的长度应该是离散化前的y坐标（实际长度）。
		else len[i] = len[i0] + len[i1];
	}
} Seg;

int main()
{
	scanf("%d", &N), H.clear();
	for (int i = 1, x0, y0, x1, y1; i <= N; i++)
	{
		scanf("%d%d%d%d", &x0, &y1, &x1, &y0);//注意是左上和右下
		a[i] = Node{x0, y0, y1, 1};
		a[i+N] = Node{x1, y0, y1, -1};
		qy[++M] = y0, qy[++M] = y1;
	}
	sort(qy+1, qy + M+1), M = unique(qy+1, qy + M+1) - qy - 1;
	for (int i = 1; i <= M; i++)
		H[qy[i]] = i;//离散化
	
	Seg.init(1, 1, (N <<= 1));
	sort(a + 1, a + N + 1, cmp);
	for (int i = 1; i <= N; i++)
	{
		Seg.add(1, H[a[i].y0], H[a[i].y1] - 1, a[i].c);
		ans += (long long)Seg.len[1] * (a[i+1].x - a[i].x);
	} printf("%lld\n", ans);
}

另外，本题N规模为1000，最多2000个不同的坐标，线段树开8000是足够的，但是上面的代码如果开了O2就会WA。必须要开更大的空间才能过，如果有知道原因的dalao欢迎来踩。