洛谷P1856系列题解

题目链接

题目大意：给你n个矩形，求它们的周长并，n $\le$ 5e3，坐标范围[-1e4, 1e4]。

难度：Ag+

分析：

每个矩形可以拆成四条线段，两条水平，两条竖直。对于一个矩形拆成的两条水平线段，其左右端点的横坐标相同，纵坐标不同，把纵坐标小的叫第一类水平线段，纵坐标大的叫第二类水平线段。首先维护一个数轴，其上所有点均未被线段覆盖。然后对于所有水平的线段，按线段的纵坐标从小到大排序。遍历排好序的水平线段，对于第一类水平线段，将其插入到数轴上，对于第二类水平线段，将其对应的第一类水平线段从数轴上删除。每次插入和删除之后，统计数轴中有多少点被至少一条线段覆盖，其值和上一次统计的结果做差，差的绝对值就是对答案的贡献。（至于原因，可以画图来看一下）

对于竖直的线段，可以类比水平线段的做法。

现在问题转换成，一个数轴，三种操作：

1. 在数轴上插入一条线段
2. 在数轴上删除一条线段
3. 查询数轴上有多少个点被至少一条线段覆盖

发现可以使用线段树来维护这个数轴，线段树每个节点维护两个值a和b，a表示区间里被至少一条线段覆盖的点数，b表示区间被直接覆盖的次数。

对于操作1，线段对应的区间，可以在线段树上被拆分成一些子区间，这些子区间的对应节点的b值加1，由于这些子区间里每一个点现在都被至少一条线段覆盖了，对应节点的a值变为区间长度。

对于操作2，同操作1一样把线段对应的区间拆分成子区间，这些子区间的对应节点的b值减1，如果某个叶节点的b值被减为0，显然应该把这个叶节点的a值也赋为0，如果某个非叶节点的b值被减为0，则该节点的a值等于其左右子节点的a值之和（因为虽然没有线段直接覆盖该区间，但有可能直接覆盖该区间的子区间）。

对于操作3，直接返回根节点的a值。

复杂度：O(nlogm)，n表示矩形数，m表示坐标范围

代码：

# include <bits/stdc++.h>
# define MAXN 20005

using namespace std;

struct Line
{
	int pos, x, y, val;	//pos表示线段的横（纵）坐标，x和y分别表示两个端点的纵（横）坐标，val表示应该插入还是删除

	bool operator < (const Line & l) const
	{
		if (pos == l.pos)
			return val > l.val;	//先插入，再删除
		return pos < l.pos;
	}
};

struct SGT
{
	int n;
	int a[2][MAXN << 2];	//a[0]表示区间里被覆盖的点数，a[1]表示区间直接被覆盖的次数

	void build(int size)
	{
		n = size;
		for (int i = 0; i < 2; ++i)
			memset(a[i], 0, sizeof(int) * n * 4);
	}

	void push_up(int cur)
	{
		if (!a[1][cur])	//如果区间未被直接覆盖过，区间里被覆盖的点数等于左右子区间里被覆盖的点数之和
			a[0][cur] = a[0][cur << 1] + a[0][(cur << 1) | 1];
	}

	void update(int x, int y, int val, int left, int right, int cur)
	{
		if (left >= x && right <= y)
		{
			a[1][cur] += val;
			if (a[1][cur])	//如果区间被直接覆盖过，区间里被覆盖的点数等于区间长度
				a[0][cur] = right - left + 1;
			else if (left == right)	//如果长度为1的区间未被直接覆盖过，被覆盖的点数等于0
				a[0][cur] = 0;
			else	//否则，区间里被覆盖的点数等于左右子区间里被覆盖的点数之和
				a[0][cur] = a[0][cur << 1] + a[0][(cur << 1) | 1];
			return;
		}
		int mid = (left + right) >> 1;
		if (x <= mid)
			update(x, y, val, left, mid, cur << 1);
		if (y > mid)
			update(x, y, val, mid + 1, right, (cur << 1) | 1);
		push_up(cur);
	}

	void update(int x, int y, int val)
	{
		update(x + 10001, y + 10001, val, 1, n, 1);
	}

	int query()
	{
		return a[0][1];	//返回整个区间里被覆盖的点数
	}
};

SGT s;
vector<Line> v1, v2;	//v1存放所有水平的线，v2存放所有竖直的线

int main()
{
	int n;
	scanf("%d", &n);
	int x1, y1, x2, y2;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		v1.push_back((Line) {y1, x1, x2, 1});
		v1.push_back((Line) {y2, x1, x2, -1});
		v2.push_back((Line) {x1, y1, y2, 1});
		v2.push_back((Line) {x2, y1, y2, -1});
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	int ans = 0;
	s.build(20001);
	int prev = 0, tmp;
	for (Line l : v1)
	{
		s.update(l.x, l.y - 1, l.val);	//注意要减1
		tmp = s.query();
		ans += abs(tmp - prev);
		prev = tmp;
	}
	s.build(20001);
	prev = 0;
	for (Line l : v2)
	{
		s.update(l.x, l.y - 1, l.val);
		tmp = s.query();
		ans += abs(tmp - prev);
		prev = tmp;
	}
	printf("%d", ans);

	return 0;
}

扩展1：

给你一个数轴，有三种操作：

1. 插入一条线段
2. 删除一条线段
3. 查询区间上有多少个点被至少一条线段覆盖

只有操作3跟原题中不一样，原题中操作3是查询数轴上有多少个点被至少一条线段覆盖。原题中对于每次操作3，直接返回线段树根节点的a值，我们先来分析这个做法的正确性。

每次插入一条线段的时候，会把这条线段对应的区间在线段树上分成一些互不相交的子区间，然后修改子区间对应节点上的a和b的值。由于要求互不相交，因此对于一个节点来说，若某条线段完全覆盖了它父节点所表示的区间，那么这个节点就不会因为这条线段的插入而被修改，所以每个节点的视角其实都有局限。具体地说，对于每个节点，它感知不到完全覆盖了它父节点所表示的区间的线段，因此每个节点所保存的a值也不一定等于它对应的区间中被至少一条线段所覆盖的点数。

那么原题中直接返回根节点的a值为什么是正确的呢？我们可以发现，根节点是一个例外，它没有父节点，因此它能感知所有线段，那么它所保存的a值也一定等于数轴上被至少一条线段所覆盖的点数。

现在问题的关键在于，我们怎么样通过不一定正确的a值，来计算区间上有多少个点被至少一条线段覆盖。考虑一个节点a值不正确的情况，这时至少有一条线段，完全覆盖了它父节点所表示的区间，那这条线段也一定覆盖了此节点，所以这种条件下该节点上正确的a值一定等于节点对应的区间长度。因此一个节点的a值只有两种情况，如果存在一条完全覆盖了它父节点所表示的区间的线段，该节点a值等于对应区间的长度，否则该节点a值一定正确。那么如何确定这样的一条线段是否存在呢？只需要查看该节点的所有祖先节点的b值，如果全为0则不存在，不全为0则存在。

至此应该就很明显了，b值完全符合一个永久化标记的定义，所以b值实际上就是一个永久化标记，问题转化成了一棵带永久化标记的线段树的区间修改和区间查询，只要熟悉永久化标记的使用，问题就迎刃而解。