P14228 [ICPC 2024 Kunming I] 漫步野径

· · 题解

首先如果没有特殊点，对于一个点 (x,y) 从 (0,0) 到它的最短路时 x + y，总答案：

\sum_{x = 0}^{p} \sum_{y = 0}^{q} {x + y} = \frac{(p + 1)(q + 1)(p + q)}{2}

然后考虑特殊点对答案的影响，显然它对于它右上角的一个矩形可以减小路径长度，但是我们发现一条特殊点也会受到其它特殊点的影响，设 g_i 表示从 (0,0) 走到第 i 个特殊点，最多经过多少个特殊点，我们把点按 x_i 排序之后就变成了一个 LIS 问题，二分优化后可以 O(n\log{n}) 的时间复杂度解决。

接下来我们考虑其他点的 g 是什么，肯定是所有可以影响到它的特殊点的最大 g_i，我们肯定让 g_i 小的先覆盖，再去覆盖大的，但是多次覆盖太难维护了，我们考虑分层计数设 S_k 表示 g \ge k 的个数，即至少可以走 k 次特殊小径的点的个数，那么 S_k 肯定是所有 g_i = k 的点可以覆盖到的矩形面积并，于是我们对于每一个 g_i = k 的特殊点在一起处理。

怎么计算面积并呢？在刚开始的时候，我们把特殊点按 x_i 升序排序，如果 x 相同按 y_i 降序排序 考虑将所有特殊点按照 x 从小到大排序，若 x 相同，则按照 y 从大到小排序。

接下来考虑 g 值相同的点具有怎样的性质。

假设同一层中存在两个点 (x_i,y_i) 和 (x_j,y_j)，满足 x_i<x_j。

若 y_i<y_j，那么第 j 个点一定可以接在第 i 个点后面，从而有：

g_j\ge g_i+1

这与 g_i=g_j 矛盾。

因此，对于同一层的任意两个点，必然满足：

x_i<x_j\implies y_i\ge y_j

因此同一层中的点一定满足：

\begin{cases} x_1\le x_2\le\cdots\le x_m,\\ y_1\ge y_2\ge\cdots\ge y_m. \end{cases}

我们运用这个性质，在扫描同一层的点的过程中，记录 lst 表示上一个点的 y_i 然后每次计算 (lst - y_i) \times (p + 1 - x_i)，就可以解决这个问题了。

这部分的时间复杂度是 O(n) 的。