题解 P4633 [POI2004]WYS
Ryo_Yamada
·
·
题解
花了两天终于搞懂了这道题 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，则有两种情况：
如何判断包含关系？一个多边形的边 (x,\,y)，标记逆时针的终点 y。若 b 有标记则 b 不被包含，否则被包含。读者自证不难 实际上分类讨论一下就可以了。
最后，如何维护每个多边形包含的区间？由于排序后的性质（x 第一关键字升序，y 第二关键字升序），多边形每条边的起点就加入到区间，终点不加入。
```cpp
#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;
}
```