自动搬运

查看原文

来自洛谷，原作者为

	Ryo_Yamada **

搬运于2025-08-24 22:02:09，当前版本为作者最后更新于2020-11-11 21:54:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

花了两天终于搞懂了这道题 qwq，来一发题解

给定 $n$ 个互不相交的多边形，问最大深度。深度的定义为：若多边形 $i$ 包含多边形 $j$ 则 $dep_i = \max\{dep_j\} + 1$。

扫描线，动态维护区间。从左向右枚举交 $x$ 轴、平行于 $y$ 轴的扫描线，维护每一个多边形在这条扫描线上包含的最大 $y$ 区间。

在任意时间这段区间都是连续的，所以只需维护两个端点即可。

将所有点按照 $x$ 为第一关键字，$y$ 为第二关键字升序排序，从小到大枚举每个点。

若当前枚举到 $a$ 点，多边形 $X$；在这些区间端点中找一个 $b$，满足 $y_b > y_a$，$b$ 最小。若 $b$ 所在多边形为 $Y$，则有两种情况：

• 若 $b$ 被当前区间包含则 $dep_X = dep_Y + 1$。

• 否则，$dep_X = dep_Y$。

如何判断包含关系？一个多边形的边 $(x,\,y)$，标记逆时针的终点 $y$。若 $b$ 有标记则 $b$ 不被包含，否则被包含。读者自证不难 实际上分类讨论一下就可以了。

最后，如何维护每个多边形包含的区间？由于排序后的性质（$x$ 第一关键字升序，$y$ 第二关键字升序），多边形每条边的起点就加入到区间，终点不加入。

$\text{Code}$：

#include <bits/stdc++.h>
#define se second
#define It iterator

using namespace std;

const int N = 4e4 + 5;
const int K = 2e5 + 5;

struct O_WYS {
	int id, x, y, f;
	O_WYS() {}
	O_WYS(int i, int _x, int _y, int fl) : id(i), x(_x), y(_y), f(fl) {}
	bool operator < (const O_WYS &oth) const {
		return x == oth.x ? y < oth.y : x < oth.x;
	} 
} sq[K];

int n, cnt, d[N], in[3], vis[N];
map<int, int> mp;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int k, tmp;
		scanf("%d%d", &k, in);
		tmp = in[0];
		for(int j = 1; j < k; j++) {
			scanf("%d", in + (j & 1));
			sq[++cnt] = O_WYS(i, in[0], in[1], (j & 1));
		}
		sq[++cnt] = O_WYS(i, tmp, in[1], (k & 1));
	}
	sort(sq + 1, sq + cnt + 1);
	for(int i = 1; i <= cnt; i++) {
		int y = sq[i].y, id = sq[i].id;
		map<int, int> :: It it = mp.find(y);
		if(it != mp.end()) mp.erase(it);
		else {
			mp[y] = i;
			if(!vis[id]) {
				it = mp.upper_bound(y);
				if(it != mp.end()) {
					if(sq[it -> se].f) vis[id] = vis[sq[it -> se].id];
					else vis[id] = vis[sq[it -> se].id] + 1;
				}
				else vis[id] = 1;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) ans = max(ans, vis[i]);
	cout << ans << endl;
	return 0;
}