「PA 2017」Giewont

0
admin LV 10 SU @ 2026-4-27 23:10:50
相对比较繁琐，但是也很有意思的一个几何题，带来了很多新的思路。我会尽量用比较少的篇幅把关键的技术细节尽量讲清楚。

2026.2.5：使用了比较有条理的小标题重新排了一下版。

下边是我自己重新翻译的题目，和站内的题面还是不太一样的。

::::info[题意重述]

我不知道为什么最后这题被翻译成了这样子，本来是一个比较有意思的情景题，结果被搞得一股概念味。

题面来自 Potyczki Algorytmiczne 2017 Runda 5 (24 November 2017, 09:00 - 27 November 2017, 00:00) Giewont [A]，由 Kimi K2.5 Thinking 重新翻译，我自己校对，仅供参考。

题目背景

知名的山地徒步爱好者 Bajtazar 即将踏上新的征程。这次他被波兰塔特拉山的照片所吸引，决定征服 Giewont 山峰。他想知道需要攀登到多高。遗憾的是，他在 Byte 国购买的地图非常不完整。

地图上唯一标注的是等高线。我们可以建立直角坐标系，每条等高线都是一条顶点坐标为整数、边与坐标轴平行的闭合简单折线。等高线之间不会相交或接触，但可以任意嵌套。我们假设存在一条“外部”等高线，包含所有其他等高线。

Bajtazar 想从地图上读取最高峰的高度，但等高线上没有标注高度。于是他决定（名符其实地*）从上往下估算高度。因为地图上的山峰由一系列彼此嵌套的等高线表示，他假设这样的嵌套序列越长，山峰就可能越高。

不幸的是，他怀疑地图只包含了部分等高线，实际山峰可能更高。他现在想在地图上补画新的等高线，以获得尽可能高的山峰。请帮助 Bajtazar 编写程序完成这个任务。新等高线必须是闭合简单折线，且满足与地图上现有等高线相同的条件（整数坐标、边与坐标轴平行、不与其他等高线相交或接触、包含在“外部”等高线内）。

输入格式

第一行是一个正整数 $n$ ，表示地图上的等高线数量。

接下来 $n$ 行，每行描述一条等高线。描述以一个偶数 $k$ 开头，表示等高线的顶点数。随后是 $k$ 个整数 $x_1,\,x_2,\,\cdots,\,x_k\ (-10^8\le x_i\le10^8)$ 。等高线的顶点依次为：
$$(x_1,\,x_2),(x_3,\,x_2),(x_3,\,x_4),(x_5,\,x_4),\cdots,(x_{k-1},\,x_k),(x_1,\,x_k)$$
所有等高线的顶点总数不超过 $50000$ 。等高线以任意顺序给出。按顶点顺序遍历任意一条等高线时，其内部始终位于左侧。

输出格式

输出一个整数，表示通过补画新等高线能得到的最高山峰的高度（即最长的嵌套等高线序列的长度）。

样例

输入
```
6
4 3 5 6 8
8 7 4 9 5 8 6 9 7
4 13 5 14 6
10 8 1 17 12 8 11 0 2 4 0
4 11 4 15 8
4 10 10 13 11
```
输出
```
5
```
样例解释

图中实线表示地图上原有的等高线。地图上已有一座由三条嵌套等高线构成的山峰。补画三条新等高线（虚线）后，可以得到由五条嵌套等高线构成的山峰。

关于加“*”内容

原文中：oszacować tę wysokość (nomen omen) z góry

原意是双关语：“nomen omen”字面即“名字就说明了”——他叫 Bajtazar，听起来像“从上方”（z góry）。

::::

尽力包括了很多要点，但并不是面面俱到的，因为这次是下定了决心要优化得非常快，很多 trick 在这里没有介绍（其实是烂大街了），感兴趣的看代码去吧。

题意与要点
- 有 $n$ 条闭合简单折线（正交多边形边界），顶点整数坐标、边平行坐标轴，互相不相交不接触，但允许嵌套，并保证存在一条“最外层”包含所有其它曲线。
- 第 $i$ 条曲线由偶数 $k$ 和 $x_1,\,x_2,\,\cdots,\,x_k$ 描述，顶点按 $(x_1,\,x_2),(x_3,\,x_2),(x_3,\,x_4),(x_5,\,x_4),\cdots,(x_{k-1},\,x_k),(x_1,\,x_k)$ 的方式给出，遍历时内部在左侧（即 CCW）。
- 可以再画任意多条同样合法的曲线（仍需在最外层内，且不与任何曲线相交或接触）。
- 输出：能获得的“最高山高度”，即最长嵌套链长度（包含关系一层套一层，计条数）。
- 坐标可达 $\pm10^8$ ，所有曲线顶点总数 $\le5\times10^4$ 。
建模的核心（离散化）

思路都是围绕这一点展开的，也很好理解：即把“画等高线”变成求“最大海拔”，这也是整题可做的原因。

$L_{\infty}$ 距离

把平面离散为网格格子，并允许从一个格子走到8个相邻格子（含对角）。

显然，两个格子间的最短距离就是切比雪夫距离：
$$\text{dist}_{\infty}((x_1,\,y_1),\,(x_2,\,y_2))=\max(|x_1-x_2|,\,|y_1-y_2|)$$
若海拔函数 $\operatorname{H}$ 满足“相邻格高度差 $\le1$ ”，则等价于：
$$|\operatorname{H}(u)-\operatorname{H}(v)|\le\text{dist}_{\infty}(u,\,v)$$
每条曲线是断层

对每条曲线 $i$ ，定义它外侧贴边那一圈格子的集合 $B_i$ 。约束是：
- $B_i$ 上的海拔都是同一个常数，我们记为 $w[i]$ 。
- 内侧贴边的那一圈格子海拔都是 $w[i]+1$ 。
- 最外侧曲线 $s$ 的海拔固定为 $0$ ，即 $w[s]=0$ 。
答案的简单证明
- 如果能造出某个点海拔为 $T$ ，那么从 $0$ 到 $T$ 的每一级分界线都能当作一条等高线（题目允许补画），自然就能得到 $T$ 层嵌套。
- 反过来想其实也一样，如果能画出 $T$ 层嵌套，从外向内跨过每层高度 +1，必然存在海拔至少为 $T$ 的点。
所以题目等价为：

在这些约束下， $\max\operatorname{H}$ 最大能是多少？

阶段性目标

这就是我们定下来的算法主线：
1. 先求每条曲线外侧能抬到的最高高度 $w[i]$ 。
2. 再用 $w[i]$ 求全局最大海拔，即答案。
Phase 1

万事开头难。

根源不等式

令 $B_i$ 为曲线 $i$ 外贴边格子的集合。定义两曲线间几何距离：
$$d(i,\,j)=\min_{u\in B_i,\,v\in B_j}\text{dist}_{\infty}(u,\,v)$$
因为 $\operatorname{H}$ 变化速率恒 $\le1$ ，且 $B_i$ 上高度恒为 $w[i]$ ，所以必有重要不等式：
$|w[i]-w[j]|\le d(i,j)$
并且根曲线 $s$ 满足 $w[s]=0$ 。

把绝对值拆开：
$$w[j]\le w[i]+d(i,\,j),\quad w[i]\le w[j]+d(i,\,j)$$
把每条曲线当作图上的点，边权为 $d(i,\,j)$ ，这就是一个完全图上的差分约束：
- 沿任意路径 $s\rightarrow\cdots\rightarrow i$ 累加可得 $w[i]\le$ 这条路径长度。
- 所以 $w[i]\le\text{dist}(s,\,i)$ （最短路距离）。
- 反过来，若定义 $w[i]=\text{dist}(s,\,i)$ ，最短路的三角不等式保证所有约束成立。
因此：

问题 1 等价于：在完全图上从 $s$ 做单源最短路，根是最外层曲线。

Attention 1

到这里有一个疑问点，也是我最开始写代码 WA 的地方，为什么树形 DP 或只看包含树不行？
- 虽然题目保证等高线嵌套关系是树形的，但是几何上的相邻（距离最近）也可能产生额外的边，也就不能用树形 DP 了。
- 常规的树形 DP 不能解决多个约束取交集的情况，即只能处理单父节点。
- 树形 DP 也不适用于后续的可行性检查（二分），这块不详细展开讲了。
其实最关键的限制就在于约束发生在任意两条曲线之间（尤其是同层兄弟曲线彼此很近时，会横向卡高度差），不是只靠父子关系能传递的。

Attention 2

注意 $d(i,\,j)$ 是集合间的最小距离，不满足三角不等式，也就是说这里描述的曲线距离不是度量。

Phase 1 的难点

也是我个人认为整个题最难的地方：

关键的问题是完全图 $\mathcal{O}(n^2)$ 太大，怎么不算 $d(i,\,j)$ 的所有对？

方法一：KD-tree

把段／点转成高维点，边权是切比雪夫距离，用 KD-tree 动态找最优松弛点，整体就是几何最短路加速。

高维（这里是四维）KD-tree 比较难写，而且写出来经常由于不明原因坠机（可能是同曲线过滤之类的），另外 $\mathcal{O}(n^{1.75})$ 的复杂度写不好也容易 TLE。

方法二：让我们拆的更碎一点

考虑利用几何性质构造一个稀疏但保距的图，我们不需要所有边，只需要能支撑 Dijkstra 得到正确最短路的关键边作为候选边就足够了。

我们知道，两条正交多边形边界的最小 $L_{\infty}$ 距离一般来自两类情况：
1. 平行边投影重叠（水平—水平／竖直—竖直）：最近距离就是纯竖直／水平间距。
2. 角附近／投影不重叠：最近距离出现在某个方向的“最近点”（点—点／点—段）。
所以我们可以分开维护这两类情况，最后合在一起就可以覆盖所有情况了，后续让我们把它们简称为第一类／第二类情况。

后续我会结合我代码中的内容，以方法二作展开，分别用两个模块维护这两类情况，这里就不提前过多展开了。

外侧边界的表示法

只是一些技术细节，但是这几块想写好免不了多调，所以结合我的代码稍微讲多一点，高手应该可以轻松搞好。

坐标平移法
- 取所有输入数的全局最小值 $mn$ ，令 $L=2$ ，把所有坐标作平移： $x\leftarrow x-(mn-L)$ ，这样保证坐标非负，留出点余量也防止后期操作的时候跑到负数区域去。
- 取平移后最大坐标 $m_0$ ，令 $m=m_0+L+1$ 。用 $[0,\,m-1]^2$ 来作为后续的统一的处理区域。
快速找 rt（根）

一个比较显然的结论：如果某条曲线的输入数列里出现 $L$ ，那么它一定是根。

因为平移后全局最小坐标值就是 $L$ ，根据题目，存在一条曲线包含所有其他曲线且互不接触，所以只有最外层可能触及全局最小坐标（内层都被包在里边，不可能触及这个最小值）。

这样省的算面积了。

还原输入

题面顶点是交替给出的，我们可以用一些简单的规则将其还原为点列 v[j]：
- 当 $j$ 为奇／偶时， $x$ 和 $y$ 从序列不同位置取即可。
- 最终得到的就应该是按 CCW 顺序的顶点列表。
从多边形边界得到外侧贴边格子带的线段集合

对每条边（顶点 $a\rightarrow b$ ），根据方向决定外侧在哪一边，然后把它转换成一个轴对齐线段，收集到线段集合 f[i] 中。在实现过程中应该注意一些细节，这里给出我代码中的两个关键点。

关键点 1：凹角的处理

应当在端点截断，避免在拐角处重叠或者漏算。

在顶点 $b$ 处看三点 $a,\,b,\,r$ ：如果不是左转（即凹角），就把当前边的终点 $b$ 沿着边的方向回退一格即可（水平改 $x$ 竖直改 $y$ ）。

如果简单都算满的话会出现重复覆盖或错误链接等问题。

关键点 2：方向对应的整体偏移

注意：只是我自己的代码在实现的时候选择的一种一致化编码，不唯一，仅供参考，当然可以选别的，只不过这样编比较符合正常人的直觉，后续也都按照这个规则展开叙述。

把外侧贴边带映射到整数坐标系中（用于后续 $L_{\infty}$ 距离计算），对边方向做如下偏移：
- 走右：整体 $y\leftarrow y-1$ 。
- 走左：整体 $x\leftarrow x-1$ 。
- 走下：整体 $(x,\,y)\leftarrow(x-1,\,y-1)$
- 走上：不偏移。
只要你对每条边外侧贴边带的离散化规则全程一致（不一定非是我这一种），那么后续用 $L_{\infty}$ 距离计算曲线间约束就成立；凹角处的端点修也正是保证一致性的关键。

采样点 c[i]

每条边处理完成后，我们把（修正后的）端点 $b$ 放进 c[i]。

这些点后续会用于两件事（这块可以看完后边回头看或者结合起来看，简要说就是后续的两个模块都需要它）：
- 扫描线中作为“查询点”，找与活跃平行边的最近间距。
- 方向最近邻中作为“点集”，做多个方向的近邻候选。
采样点取每条边一个端点已经足够了，当平行边投影重叠时，重叠区间的端点总属于某条边的端点，即最短距离一定能在某个端点处被捕捉到。

候选边生成模块 A：扫描线

这一部分被专门用于抓住前边所讲的第一类情况的约束，引用我代码中的名称来简要介绍。

关于扫描线中的 gh
- 收集所有水平线段：对每条水平段 $(x_1,\,y)\rightarrow(x_2,\,y)$ 产生事件：
 
 A：在 $x=x_1$ 插入。
 
 D：在 $x=x_2$ 删除。
- 对每个采样点 $(x,y)$ 产生查询事件 Q。
按 $x$ 排序，同 $x$ 时顺序A $\rightarrow$ Q $\rightarrow$ D，这样线段在端点也视作活跃。

维护一个按 $y$ 排序的 multiset<pii> st。对每个查询点，只需要看：
- $y$ 的前驱（最近的下方段）。
- $y$ 的后继（最近的上方段）。
因为在同 $x$ 下，最近的垂直距离一定来自最近 $y$ 的那两条水平段。

得到的候选边权就是 $|y-y_{seg}|$ （此时 $x$ 投影重叠）。

关于扫描线中的 gs

gh 只处理水平段，如果想处理竖直段，作简单的坐标变换：
$(x,\,y)\leftrightarrow(y,\,x)$
随后就可以直接复用 gh 了。

候选边生成模块 B：方向最近邻 NEH

来到了整个题最复杂也最重要的部分了，这一部分被专门用于抓住前边所讲的第二类情况的约束，同样引用我代码中的名称来简要介绍。

目标

我们最终想要连接可能给出最紧约束的曲线对。当最短距离不来自平行投影重叠时，常见的情况是：
- 最近点落在某个拐角附近
- 表现为：对某个边界点 $p$ ，另一条曲线的最近点 $q$ 位于 $p$ 的某个方向（NE／NW／SE／SW 等）并且在该方向里最靠近。
事实上这类似于曼哈顿 MST：只需维护每个点在若干方向的最优候选，就能得到足够密集的几何骨架。

所以只需要对每个点输出一些候选即可，后边用它们形成曲线级别边。

先固定一个象限

我们只讲东北（NE）。

对点 $p=(x,\,y)$ ，考虑所有满足 $x'\ge x,\,y'\ge y$ 的候选点 $q=(x',\,y')$ 。

$L_{\infty}$ 距离：
$d_{\infty}(p,\,q)=\max(x'-x,\,y'-y)$
NE 里有两类主导情况：
- $dx$ 主导： $x'-x\ge y'-y\Rightarrow$ 距离等于 $x'-x$ ，要最小则尽量减小 $x'$ 。
- $dy$ 主导： $y'-y\ge x'-x\Rightarrow$ 距离等于 $y'-y$ ，要最小则尽量减小 $y'$ 。
考虑用 $s=y-x$ 把 NE 拆成两块（也是坐标变换的核心）。

然后我们就可以推出一个重要等价式：
$$(y'-y)\ge(x'-x)\Longleftrightarrow(y'-x')\ge(y-x)\Longleftrightarrow s'\ge s$$
所以根据该式，NE 的拆法很明显了：
1. $s'\le s$ ： $dx$ 主导区，目标最小 $x'$ 。
2. $s'\ge s$ ： $dy$ 主导区，目标最小 $y'$ 。
显然，这已经很像是二维支配查询了：
- 约束是“ $y$ 不小于某值”和“ $s$ 不大于／不小于某值”。
- 目标是最小 $x$ 或最小 $y$ 。
考虑用 2D Fenwick，即 BIT on BIT 来维护（线段树也一样，甚至这一步也可以考虑 KD-tree 但复杂度差）。

一些小细节

只是介绍偏常用的技巧，不是什么很新的思路。

考虑把 $\ge$ 变得更好做

选定了 2D Fenwick，众所周知 Fenwick 做“前缀 $[1\dots k]$ ”更方便，而我们要的是 $y'\ge y$ 。考虑一个常用的做法，把 $y$ 的 rank 反过来：
- 压缩 $y$ 从小到大得到 rank $ry$ 。
- 定义反向 rank： $yr=ny-ry+1$
则我们可以得到等价式：
$$y'\ge y\Longleftrightarrow ry'\ge ry\Longleftrightarrow yr'\le yr$$
于是 $y'\ge y$ 就通过如上变换成了前缀条件。

对于 $s$ 条件也是同理，这里不展开了。

此时为了保证 $x'\ge x$ ，按 $x$ 从大到小离线扫即可，用排序把一个维度的约束消掉，就不用动态维护了。

根据以上讨论，我们使用两棵 2D Fenwick，都是做二维前缀查询，一颗负责 $dx$ 主导，一颗负责 $dy$ 主导，维护的对象也不同。

关于 $y$ 的覆盖

注意到我们最后加边是无向的（ $g[u]$ 和 $g[v]$ 都加），所以当 $q$ 在 $p$ 的南边（即 $y'\le y$ ），那么从 $q$ 看 $p$ 就在北边，最终会在以 $q$ 为查询点的那次被捕捉到，再因为边无向而等效。

所以实际上由于对称性， $y$ 不需要通过坐标变换来覆盖另一半，我们只做半平面查询即可覆盖全方向。

关于 $x$ 的覆盖

以上讨论的结构覆盖 $x'\ge x$ （右侧），想要覆盖左侧，考虑坐标变换：
$(x,\,y)\mapsto(-x,\,y)$
那么 $x'\le x$ 变成 $-x'\ge-x$ ，就可以继续复用同一套 NE 查询了。

关于每个 Fenwick 节点的候选数

这一块也是需要调出来的地方，而且不是很好证明，单独拿出来简要说一下。

查询要求最近点必须来自其它曲线，但是事实上最优的候选很容易出现在同一条曲线上，不能用来连曲线边。

所以我们考虑 Fenwick 的每个节点不只维护一个最优候选，而是维护来自不同曲线的前四名，查询时过滤掉曲线 id 相同的点，再从剩下里挑最优，最多取四个，保证都能拿到有效候选，防止建出来的图断边。

注意上边的“前四名”和“四个”并不是逐个试出来的，因为改维护点也不是特别方便，所以在两个 WA 之后我就直接跳到四个了，三个的情况我没试。

构筑稀疏图后得到 $w[i]$

跑 Dijkstra 即可，注意到扫描线和方向最近邻均会产生一些重复的 $(u,\,v)$ ，对每个 $u$ 的邻接表排序后，把同一 $v$ 边权取最小即可显著降低实际边数和堆操作数。

最后计算出的 dist[i] 即我们第一阶段的最终目标 $w[i]$ 。

Phase 2

并不是难点，如果不考虑优化的话这里偏套路化，二分配合覆盖判定，稍微推一下公式就足够了，如果能解决 Phase 1，这里一般卡不到你。

公式推导

对任意点 $p$ ，由于从 $B_i$ 走到 $p$ 至少需要 $\text{dist}_{\infty}(p,\,B_i)$ 步，每步最多 +1：
$$\operatorname{H}(p)\le w[i]+\text{dist}_{\infty}(p,\,B_i)$$
所以全局上界取最小：
$$\operatorname{H}(p)\le\min_i(w[i]+\text{dist}_{\infty}(p,\,B_i))$$
即得：
$$\text{Ans}=\max_p\min_i(w[i]+\text{dist}_{\infty}(p,\,B_i))$$
二分与禁区

对目标高度 $T$ ，判断是否存在点 $p$ 在根内部满足 $\operatorname{H}(p)\ge T$ ：

显然对任意曲线 $i$ ，若存在：
$w[i]+\text{dist}_{\infty}(p,\,B_i)\le T-1$
则必定达不到 $T$ 。

让我们令：
$r_i=T-w[i]-1$
显然若 $\text{dist}_{\infty}(p,\,B_i)\le r_i$ 的区域把根内部全都覆盖则不可行，将其定义为禁区。

显然可行性关于 $T$ 单调，二分 $T$ 即可。

参考代码

虽然我觉得要点讲的足够细致了，但是还是有一些 trick 没讲，比如 radix sort（rsi rs32 rse），开放寻址哈希，对于根外部的预处理（br）等。

时间复杂度约 $\mathcal{O}(N\log^2N)$ ，瓶颈在 Phase 1 中 NEH 的离线 2D Fenwick，不保证时间复杂度最优。

整理后的代码在 Szkopuł 重新提交（1.8s/15s），可以看到数据强度比洛谷要大得多，也证明了 NEH 中每个点返回四个候选绝对是足够的。
```
#include<bits/stdc++.h>
using namespace std;
struct FS{
	static const int S=1<<20;
	int i,n;
	char b[S];
	FS():i(0),n(0){}
	inline char gc(){
		if(i>=n){
			n=fread(b,1,S,stdin);
			i=0;
			if(!n) return 0;
		}
		return b[i++];
	}
	template<class T> inline bool rd(T& o){
		char c;
		do{
			c=gc();
			if(!c) return 0;
		}
		while(c!='-'&&(c<'0'||c>'9'));
		int s=1;
		if(c=='-'){
			s=-1;
			c=gc();
		}
		long long v=0;
		while(c>='0'&&c<='9'){
			v=v*10+(c-'0');
			c=gc();
		}
		o=(T)(v*s);
		return 1;
	}
}fs;
struct P{
	int x,y;
};
static inline long long dt(P a,P b){
	return 1ll*a.x*b.y-1ll*a.y*b.x;
}
static inline P sb(P a,P b){
	return {a.x-b.x,a.y-b.y};
}
static inline bool lf(P a,P b,P c){
	return dt(sb(b,a),sb(c,b))>0;
}
static inline int d8(int ax,int ay,int bx,int by){
	int x=ax-bx;
	if(x<0)x=-x;
	int y=ay-by;
	if(y<0)y=-y;
	return x>y?x:y;
}
struct ST{
	int p;
	vector<int> s,l;
	ST():p(1){}
	static inline int pa(int x){
		return (x-1)>>1;
	}
	inline void pu(int x){
		s[x]=min(s[x*2+1]+l[x*2+1],s[x*2+2]+l[x*2+2]);
	}
	inline void init(int n){
		int np=1;
		while(np<n) np<<=1;
		p=np;
		int sz=2*p-1;
		if((int)s.size()<sz){
			s.resize(sz);
			l.resize(sz);
		}
		memset(s.data(),0,sz*sizeof(int));
		memset(l.data(),0,sz*sizeof(int));
		int b=p-1;
		for(int i=n;i<p;i++) l[b+i]=1000000000;
		for(int x=b-1;x>=0;x--) pu(x);
	}
	inline void ad(int a,int b,int v){
		a+=p-1;
		b+=p-1;
		l[a]+=v;
		if(a<b) l[b]+=v;
		while(pa(a)!=pa(b)){
			if(a&1) l[a+1]+=v;
			if(!(b&1)) l[b-1]+=v;
			a=pa(a);
			b=pa(b);
			pu(a);
			pu(b);
		}
		while(a){
			a=pa(a);
			pu(a);
		}
	}
	inline int mn(){
		return s[0]+l[0];
	}
}st;
struct R{
	int a,b,c,d;
};
struct Ev{
	int x,l,r,v;
};
static inline void rs32(vector<int>& a){
	static vector<int> b;
	static int c[1<<16];
	int n=a.size();
	if((int)b.size()<n) b.resize(n);
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++) c[(unsigned)a[i]&65535]++;
	int s=0;
	for(int i=0;i<(1<<16);i++){
		int t=c[i];
		c[i]=s;
		s+=t;
	}
	for(int i=0;i<n;i++){
		unsigned k=(unsigned)a[i]&65535;
		b[c[k]++]=a[i];
	}
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++) c[((unsigned)b[i]>>16)&65535]++;
	s=0;
	for(int i=0;i<(1<<16);i++){
		int t=c[i];
		c[i]=s;
		s+=t;
	}
	for(int i=0;i<n;i++){
		unsigned k=((unsigned)b[i]>>16)&65535;
		a[c[k]++]=b[i];
	}
}
static inline void rsi(vector<int>& a,const vector<int>& k,int desc){
	static vector<int> b;
	static int c[1<<16];
	int n=a.size();
	if((int)b.size()<n) b.resize(n);
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++){
		unsigned x=((unsigned)k[a[i]]^0x80000000u);
		if(desc) x=~x;
		c[x&65535]++;
	}
	int s=0;
	for(int i=0;i<(1<<16);i++){
		int t=c[i];
		c[i]=s;
		s+=t;
	}
	for(int i=0;i<n;i++){
		unsigned x=((unsigned)k[a[i]]^0x80000000u);
		if(desc) x=~x;
		b[c[x&65535]++]=a[i];
	}
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++){
		unsigned x=((unsigned)k[b[i]]^0x80000000u);
		if(desc) x=~x;
		c[(x>>16)&65535]++;
	}
	s=0;
	for(int i=0;i<(1<<16);i++){
		int t=c[i];
		c[i]=s;
		s+=t;
	}
	for(int i=0;i<n;i++){
		unsigned x=((unsigned)k[b[i]]^0x80000000u);
		if(desc) x=~x;
		a[c[(x>>16)&65535]++]=b[i];
	}
}
static inline void rse(vector<Ev>& a){
	static vector<Ev> b;
	static int c[1<<16];
	int n=a.size();
	if((int)b.size()<n) b.resize(n);
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++) c[(unsigned)a[i].x&65535]++;
	int s=0;
	for(int i=0;i<(1<<16);i++){
		int t=c[i];
		c[i]=s;
		s+=t;
	}
	for(int i=0;i<n;i++){
		unsigned k=(unsigned)a[i].x&65535;
		b[c[k]++]=a[i];
	}
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++) c[((unsigned)b[i].x>>16)&65535]++;
	s=0;
	for(int i=0;i<(1<<16);i++){
		int t=c[i];
		c[i]=s;
		s+=t;
	}
	for(int i=0;i<n;i++){
		unsigned k=((unsigned)b[i].x>>16)&65535;
		a[c[k]++]=b[i];
	}
}
static inline bool ok(int m,const vector<R>& base,const vector<R>& add){
	static vector<int> y;
	static vector<Ev> e;
	static vector<int> hk,hv;
	static int hs=0;
	int needY=((int)base.size()+(int)add.size())*2+1;
	if((int)y.capacity()<needY) y.reserve(needY);
	y.clear();
	y.push_back(0);
	auto py=[&](const R& r){
		y.push_back(r.c);
		if(r.d<m-1) y.push_back(r.d+1);
	};
	for(auto &r:base) py(r);
	for(auto &r:add) py(r);
	rs32(y);
	y.erase(unique(y.begin(),y.end()),y.end());
	int t=(int)y.size();
	int need=1;
	while(need<t*2) need<<=1;
	if(need!=hs){
		hs=need;
		hk.assign(hs,-1);
		hv.assign(hs,0);
	}
	else fill(hk.begin(),hk.end(),-1);
	int mask=hs-1;
	for(int i=0;i<t;i++){
		int key=y[i];
		unsigned h=(unsigned)key*2654435761u;
		int p=(int)(h&mask);
		while(hk[p]!=-1) p=(p+1)&mask;
		hk[p]=key;
		hv[p]=i;
	}
	auto gi=[&](int key)->int{
		unsigned h=(unsigned)key*2654435761u;
		int p=(int)(h&mask);
		while(hk[p]!=key) p=(p+1)&mask;
		return hv[p];
	};
	int needE=((int)base.size()+(int)add.size())*2;
	if((int)e.capacity()<needE) e.reserve(needE);
	e.clear();
	auto pe=[&](const R& r){
		int l=gi(r.c);
		int rr=(r.d==m-1)?t-1:gi(r.d+1)-1;
		e.push_back({r.a,l,rr,1});
		if(r.b<m-1) e.push_back({r.b+1,l,rr,-1});
	};
	for(auto &r:base) pe(r);
	for(auto &r:add) pe(r);
	rse(e);
	st.init(t);
	for(int i=0;i<(int)e.size();i++){
		st.ad(e[i].l,e[i].r,e[i].v);
		if(i==(int)e.size()-1||e[i+1].x!=e[i].x){
			if(st.mn()==0) return 1;
		}
	}
	return 0;
}
using S=pair<P,P>;
static vector<R> br(int m,vector& v){
	struct I{
		int l,r,x;
		bool operator<(I const&o)const{
			return tie(l,r,x)<tie(o.l,o.r,o.x);
		}
	};
	struct E{
		int x,l,r;
		bool in;
	};
	vector<E> e;
	int s=(int)v.size();
	e.reserve(s+1);
	for(int i=0;i<s;i++){
		P p=v[i],q=v[(i+1)%s];
		if(p.x!=q.x) continue;
		int l=p.y,r=q.y;
		if(l>r) swap(l,r);
		e.push_back({p.x,l,r,q.y<p.y});
	}
	e.push_back({m,0,m,1});
	sort(e.begin(),e.end(),[](const E&a,const E&b){return a.x<b.x;});
	set st={{0,m,0}};
	vector<R> r;
	auto ct=[&](int p){
		auto it=st.lower_bound({p,-1,-1});
		if(it!=st.end()&&it->l==p) return;
		--it;
		if(it->r==p) return;
		auto u=*it;
		st.erase(it);
		st.insert({u.l,p,u.x});
		st.insert({p,u.r,u.x});
	};
	for(auto &x:e){
		if(x.in){
			ct(x.l);
			ct(x.r);
			auto a=st.lower_bound({x.l,-1,-1});
			auto b=st.lower_bound({x.r,-1,-1});
			for(auto it=a;it!=b;++it) r.push_back({it->x,x.x-1,it->l,it->r-1});
			st.erase(a,b);
		}
		else st.insert({x.l,x.r,x.x});
	}
	return r;
}
static void gh(vector<vector<S>> f,vector<vector> c,vector<vector<pair<int,int>>>& g){
	multiset<pair<int,int>> st;
	struct E{
		int u,x,y,t;
	};
	const int A=0,Q=1,D=2;
	vector<E> e;
	for(int u=0;u<(int)f.size();u++) for(auto &s:f[u]){
		P p=s.first,q=s.second;
		if(p.y!=q.y) continue;
		e.push_back({u,p.x,p.y,A});
		e.push_back({u,q.x,q.y,D});
	}
	for(int u=0;u<(int)c.size();u++) for(auto &p:c[u]) e.push_back({u,p.x,p.y,Q});
	sort(e.begin(),e.end(),[](const E&a,const E&b){return a.x!=b.x?a.x<b.x:a.t<b.t;});
	for(auto &x:e){
		if(x.t==A) st.insert({x.y,x.u});
		else if(x.t==D) st.erase(st.find({x.y,x.u}));
		else{
			auto it=st.lower_bound({x.y,-1});
			if(it!=st.begin()) --it;
			while(it!=st.end()){
				int u=x.u,v=it->second;
				if(u!=v){
					int w=x.y-it->first;
					if(w<0) w=-w;
					g[u].push_back({v,w});
					g[v].push_back({u,w});
				}
				if(it->first>x.y) break;
				++it;
			}
		}
	}
}
static void gs(int n,vector<vector<S>> f,vector<vector> c,vector<vector<pair<int,int>>>& g){
	gh(f,c,g);
	auto fp=[&](P &a){
		swap(a.x,a.y);
	};
	auto fs=[&](S &s){
		fp(s.first);
		fp(s.second);
	};
	for(auto &x:f) for(auto &s:x) fs(s);
	for(auto &x:c) for(auto &p:x) fp(p);
	gh(f,c,g);
}
static vector<int> dj(int s,vector<vector<pair<int,int>>>& g){
	const int I=1000000001;
	int n=(int)g.size();
	vector<int> d(n,I);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	d[s]=0;
	q.push({0,s});
	while(!q.empty()){
		auto [w,u]=q.top();
		q.pop();
		if(w!=d[u]) continue;
		for(auto [v,c]:g[u]){
			int nw=w+c;
			if(nw<d[v]){
				d[v]=nw;
				q.push({nw,v});
			}
		}
	}
	return d;
}
static const int IV=1000000001;
struct C{
	int v,p,i;
};
struct N4{
	C a,b,c,d;
};
static inline void in4(N4& x){
	x.a={IV,-1,-1};
	x.b={IV,-1,-1};
	x.c={IV,-1,-1};
	x.d={IV,-1,-1};
}
static inline void fix4(N4& x){
	if(x.b.v<x.a.v) swap(x.a,x.b);
	if(x.c.v<x.b.v) swap(x.b,x.c);
	if(x.b.v<x.a.v) swap(x.a,x.b);
	if(x.d.v<x.c.v) swap(x.c,x.d);
	if(x.c.v<x.b.v) swap(x.b,x.c);
	if(x.b.v<x.a.v) swap(x.a,x.b);
}
static inline void add4(N4& x, C c){
	if(c.v>=IV) return;
	if(x.a.p==c.p){
		if(c.v<x.a.v) x.a=c;
		fix4(x);
		return;
	}
	if(x.b.p==c.p){
		if(c.v<x.b.v) x.b=c;
		fix4(x);
		return;
	}
	if(x.c.p==c.p){
		if(c.v<x.c.v) x.c=c;
		fix4(x);
		return;
	}
	if(x.d.p==c.p){
		if(c.v<x.d.v) x.d=c;
		fix4(x);
		return;
	}
	if(c.v>=x.d.v) return;
	x.d=c;
	fix4(x);
}
static inline void mg4(N4& x,const N4& y){
	add4(x,y.a);
	add4(x,y.b);
	add4(x,y.c);
	add4(x,y.d);
}
struct B4{
	int n,m,pn,pm;
	const int* y0,*py;
	vector<vector<int>> xs;
	vector<vector<N4>> t;
	vector<int> cnt,uo,qo,up,qp,last,ub;
	static inline int lb(int v){
		return v&-v;
	}
	B4():n(0),m(0),pn(0),pm(0),y0(nullptr),py(nullptr){}
	void bd2(int n_,int m_,const int* y,const int* z,const vector<int>& o,int rev){
		n=n_;
		m=m_;
		y0=y;
		if((int)xs.size()<n+1){
			xs.resize(n+1);
			t.resize(n+1);
			cnt.resize(n+1);
		}
		else{
			xs.resize(n+1);
			t.resize(n+1);
		}
		if(pm!=m||pn!=n||py!=y){
			uo.assign(m+1,0);
			qo.assign(m+1,0);
			for(int k=0;k<m;k++){
				int l=0;
				for(int i=y[k];i<=n;i+=lb(i)) l++;
				uo[k+1]=uo[k]+l;
				l=0;
				for(int i=y[k];i>0;i-=lb(i)) l++;
				qo[k+1]=qo[k]+l;
			}
			pm=m;
			pn=n;
			py=y;
		}
		if((int)up.size()<uo[m]) up.resize(uo[m]);
		if((int)qp.size()<qo[m]) qp.resize(qo[m]);
		memset(cnt.data(),0,(n+1)*sizeof(int));
		for(int k=0;k<m;k++) for(int i=y[k];i<=n;i+=lb(i)) cnt[i]++;
		for(int i=1;i<=n;i++){
			auto &v=xs[i];
			v.clear();
			v.reserve(cnt[i]);
		}
		if((int)last.size()<n+1) last.resize(n+1);
		for(int i=0;i<=n;i++) last[i]=-1;
		if(!rev){
			for(int kk=0;kk<m;kk++){
				int k=o[kk],zz=z[k];
				int ptr=uo[k];
				for(int i=y[k];i<=n;i+=lb(i)){
					if(zz!=last[i]){
						last[i]=zz;
						xs[i].push_back(zz);
					}
					up[ptr++]=(int)xs[i].size();
				}
			}
		}
		else{
			for(int kk=m-1;kk>=0;kk--){
				int k=o[kk],zz=z[k];
				int ptr=uo[k];
				for(int i=y[k];i<=n;i+=lb(i)){
					if(zz!=last[i]){
						last[i]=zz;
						xs[i].push_back(zz);
					}
					up[ptr++]=(int)xs[i].size();
				}
			}
		}
		static N4 emp;
		static int init=0;
		if(!init){
			in4(emp);
			init=1;
		}
		for(int i=1;i<=n;i++) t[i].assign(xs[i].size()+1,emp);
		if((int)ub.size()<n+1) ub.resize(n+1);
		memset(ub.data(),0,(n+1)*sizeof(int));
		if(!rev){
			for(int kk=0;kk<m;kk++){
				int k=o[kk],zz=z[k];
				int ptr=qo[k];
				for(int i=y[k];i>0;i-=lb(i)){
					auto &v=xs[i];
					int u=ub[i];
					while(u<(int)v.size()&&v[u]<=zz) u++;
					ub[i]=u;
					qp[ptr++]=u;
				}
			}
		}
		else{
			for(int kk=m-1;kk>=0;kk--){
				int k=o[kk],zz=z[k];
				int ptr=qo[k];
				for(int i=y[k];i>0;i-=lb(i)){
					auto &v=xs[i];
					int u=ub[i];
					while(u<(int)v.size()&&v[u]<=zz) u++;
					ub[i]=u;
					qp[ptr++]=u;
				}
			}
		}
	}
	inline void upk(int k,C c){
		int ptr=uo[k];
		for(int i=y0[k];i<=n;i+=lb(i)){
			int p=up[ptr++];
			auto &ti=t[i];
			for(int j=p;j<(int)ti.size();j+=lb(j)) add4(ti[j],c);
		}
	}
	inline N4 qrk(int k){
		N4 r;
		in4(r);
		int ptr=qo[k];
		for(int i=y0[k];i>0;i-=lb(i)){
			int p=qp[ptr++];
			auto &ti=t[i];
			for(int j=p;j>0;j-=lb(j)) mg4(r,ti[j]);
		}
		return r;
	}
};
struct NEH{
	int n,ny;
	vector<int> y,yr,p,x,s,sr,tr,o,id;
	vector<array<int,4>> c1,c2;
	vector<array<int,8>> nb;
	B4 bt1,bt2;
	void init(int n_,int ny_,const vector<int>& y_,const vector<int>& yr_,const vector<int>& p_){
		n=n_;
		ny=ny_;
		y=y_;
		yr=yr_;
		p=p_;
		x.resize(n);
		s.resize(n);
		sr.resize(n);
		tr.resize(n);
		o.resize(n);
		id.resize(n);
		c1.assign(n,{-1,-1,-1,-1});
		c2.assign(n,{-1,-1,-1,-1});
		nb.resize(n);
	}
	void calc(const vector<int>& cx,int sx){
		for(int i=0;i<n;i++) x[i]=sx*cx[i],s[i]=y[i]-x[i];
		iota(id.begin(),id.end(),0);
		rsi(id,s,0);
		int rk=0,pv=0x3f3f3f3f;
		for(int idx:id){
			int v=s[idx];
			if(v!=pv){
				pv=v;
				rk++;
			}
			sr[idx]=rk;
		}
		int ns=rk;
		for(int i=0;i<n;i++) tr[i]=ns-sr[i]+1;
		iota(o.begin(),o.end(),0);
		rsi(o,y,1);
		rsi(o,x,1);
		bt1.bd2(ny,n,yr.data(),sr.data(),id,0);
		int i=0;
		while(i<n){
			int j=i;
			int xv=x[o[i]];
			while(j<n&&x[o[j]]==xv) j++;
			for(int k=i;k<j;k++){
				int u=o[k];
				bt1.upk(u,{x[u],p[u],u});
			}
			for(int k=i;k<j;k++){
				int u=o[k];
				auto r=bt1.qrk(u);
				int pp=p[u],cnt=0;
				if(r.a.p!=-1&&r.a.p!=pp) c1[u][cnt++]=r.a.i;
				if(cnt<4&&r.b.p!=-1&&r.b.p!=pp) c1[u][cnt++]=r.b.i;
				if(cnt<4&&r.c.p!=-1&&r.c.p!=pp) c1[u][cnt++]=r.c.i;
				if(cnt<4&&r.d.p!=-1&&r.d.p!=pp) c1[u][cnt++]=r.d.i;
				for(;cnt<4;cnt++) c1[u][cnt]=-1;
			}
			i=j;
		}
		bt2.bd2(ny,n,yr.data(),tr.data(),id,1);
		i=0;
		while(i<n){
			int j=i;
			int xv=x[o[i]];
			while(j<n&&x[o[j]]==xv) j++;
			for(int k=i;k<j;k++){
				int u=o[k];
				bt2.upk(u,{y[u],p[u],u});
			}
			for(int k=i;k<j;k++){
				int u=o[k];
				auto r=bt2.qrk(u);
				int pp=p[u],cnt=0;
				if(r.a.p!=-1&&r.a.p!=pp) c2[u][cnt++]=r.a.i;
				if(cnt<4&&r.b.p!=-1&&r.b.p!=pp) c2[u][cnt++]=r.b.i;
				if(cnt<4&&r.c.p!=-1&&r.c.p!=pp) c2[u][cnt++]=r.c.i;
				if(cnt<4&&r.d.p!=-1&&r.d.p!=pp) c2[u][cnt++]=r.d.i;
				for(;cnt<4;cnt++) c2[u][cnt]=-1;
			}
			i=j;
		}
		for(int i=0;i<n;i++){
			nb[i]={c1[i][0],c1[i][1],c1[i][2],c1[i][3],c2[i][0],c2[i][1],c2[i][2],c2[i][3]};
		}
	}
};
int main(){
	int n;
	fs.rd(n);
	vector<vector<int>> p(n);
	int mn=IV;
	for(int i=0;i<n;i++){
		int s;
		fs.rd(s);
		p[i].resize(s);
		for(int j=0;j<s;j++){
			fs.rd(p[i][j]);
			if(p[i][j]<mn) mn=p[i][j];
		}
	}
	const int L=2;
	for(auto &v:p) for(int &x:v) x-=mn-L;
	int m=0;
	for(auto &v:p) for(int x:v) if(x>m) m=x;
	m+=L+1;
	int rt=-1;
	vector<vector<pair<P,P>>> f(n);
	vector<vector> c(n);
	vector<R> bd;
	for(int i=0;i<n;i++){
		for(int x:p[i]) if(x==L){
			rt=i;
			break;
		}
		int s=(int)p[i].size();
		vector v(s);
		for(int j=0;j<s;j++){
			int x=p[i][(j+(j&1))%s];
			int y=p[i][(j+1-(j&1))];
			v[j]={x,y};
		}
		f[i].reserve(s);
		c[i].reserve(s);
		for(int j=0;j<s;j++){
			P a=v[j],b=v[(j+1)%s],r=v[(j+2)%s];
			int d;
			if(b.x>a.x) d=1;
			else if(b.x<a.x) d=2;
			else if(b.y<a.y) d=3;
			else d=4;
			if(!lf(a,b,r)){
				if(a.x==b.x) b.y-=(b.y>a.y?1:-1);
				else b.x-=(b.x>a.x?1:-1);
			}
			if(d==1){
				a.y--;
				b.y--;
			}
			else if(d==2){
				a.x--;
				b.x--;
			}
			else if(d==3){
				a.x--;
				b.x--;
				a.y--;
				b.y--;
			}
			c[i].push_back(b);
			if(a.x>b.x||a.y>b.y) swap(a,b);
			f[i].push_back({a,b});
		}
		if(i==rt) bd=br(m,v);
	}
	vector<vector<pair<int,int>>> g(n);
	gs(n,f,c,g);
	int pc=0;
	for(int i=0;i<n;i++) pc+=(int)c[i].size();
	vector<int> cx(pc),cy(pc),cp(pc);
	int id=0;
	for(int i=0;i<n;i++) for(auto &q:c[i]){
		cx[id]=q.x;
		cy[id]=q.y;
		cp[id]=i;
		id++;
	}
	vector<int> yc=cy;
	rs32(yc);
	yc.erase(unique(yc.begin(),yc.end()),yc.end());
	int ny=(int)yc.size();
	vector<int> yr(pc);
	for(int i=0;i<pc;i++){
		int rk=(int)(lower_bound(yc.begin(),yc.end(),cy[i])-yc.begin())+1;
		yr[i]=ny-rk+1;
	}
	NEH neh;
	neh.init(pc,ny,cy,yr,cp);
	auto addDir=[&](int sx){
		neh.calc(cx,sx);
		auto &nb=neh.nb;
		for(int i=0;i<pc;i++){
			int u=cp[i];
			int ax=cx[i],ay=cy[i];
			auto &ar=nb[i];
			for(int k=0;k<8;k++){
				int j=ar[k];
				if(j<0) continue;
				int v=cp[j];
				if(u==v) continue;
				int w=d8(ax,ay,cx[j],cy[j]);
				g[u].push_back({v,w});
				g[v].push_back({u,w});
			}
		}
	};
	addDir(1);
	addDir(-1);
	for(int i=0;i<n;i++){
		auto &v=g[i];
		sort(v.begin(),v.end());
		int k=0;
		for(int j=0;j<(int)v.size();j++){
			if(!k||v[j].first!=v[k-1].first) v[k++]=v[j];
			else if(v[j].second<v[k-1].second) v[k-1].second=v[j].second;
		}
		v.resize(k);
	}
	auto dist=dj(rt,g);
	vector<R> add;
	add.reserve(60000);
	int l=1,r=m;
	while(r-l>1){
		int md=(l+r)>>1;
		add.clear();
		for(int i=0;i<n;i++) if(dist[i]<md){
			int x=md-dist[i]-1;
			for(auto &s:f[i]){
				P a=s.first,b=s.second;
				int ax=a.x-x;
				if(ax<0) ax=0;
				int bx=b.x+x;
				if(bx>=m) bx=m-1;
				int ay=a.y-x;
				if(ay<0) ay=0;
				int by=b.y+x;
				if(by>=m) by=m-1;
				add.push_back({ax,bx,ay,by});
			}
		}
		if(ok(m,bd,add)) l=md;
		else r=md;
	}
	printf("%d",l);
	return 0;
}
```

ID

11020

时间

15000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

admin

1 条题解

题目背景

输入格式

输出格式

样例

输入

输出

样例解释

关于加“*”内容

题意与要点

建模的核心（离散化）

L∞L_{\infty}L∞​ 距离

每条曲线是断层

答案的简单证明

阶段性目标

Phase 1

根源不等式

Attention 1

Attention 2

Phase 1 的难点

方法一：KD-tree

方法二：让我们拆的更碎一点

外侧边界的表示法

坐标平移法

快速找 rt（根）

还原输入

从多边形边界得到外侧贴边格子带的线段集合

关键点 1：凹角的处理

关键点 2：方向对应的整体偏移

采样点 c[i]

候选边生成模块 A：扫描线

关于扫描线中的 gh

关于扫描线中的 gs

候选边生成模块 B：方向最近邻 NEH

目标

先固定一个象限

一些小细节

考虑把 ≥\ge≥ 变得更好做

关于 yyy 的覆盖

关于 xxx 的覆盖

关于每个 Fenwick 节点的候选数

构筑稀疏图后得到 w[i]w[i]w[i]

Phase 2

公式推导

二分与禁区

参考代码

信息

状态

开发

支持

关于

还没有账户？

登录

$L_{\infty}$ 距离

快速找 `rt`（根）

采样点 `c[i]`

关于扫描线中的 `gh`

关于扫描线中的 `gs`

候选边生成模块 B：方向最近邻 `NEH`

考虑把 $\ge$ 变得更好做

关于 $y$ 的覆盖

关于 $x$ 的覆盖

构筑稀疏图后得到 $w[i]$