https://atcoder.jp/contests/abc369/tasks/abc369_f

在网格图上从 (1, 1) 开始走到 (h, w)，只能往右或往上走。有 n 个格点上有金币。求最多能收集多少金币，以及给出达到最大金币数的一个路径。

数据范围：h, w \le 2 \times 10^5, n \le 2 \times 10^5。

题解

发表于知乎： https://zhuanlan.zhihu.com/p/717601517

若 h \times w \le 10^8，则这就是一道二维线性 DP 的典型例题。但是这题 h, w 范围太大，因此尝试对这个 DP 进行优化。

滚动数组优化掉第一维，只存储第二维，也就是只存储 y 坐标上的 DP 值。对于一个固定的 x，y 可能非常稀疏，需要更新的点也只有若干几个，因此我们只枚举有金币的网格。先对所有点按 x 第一关键字、y 第二关键字排序，保证 DP 顺序。然后枚举所有点，每次遇到 (x, y) 上的金币，都可以令区间 [y, W] 上的 DP 值更新：

我们可以使用数据结构加速这一“区间取最大值”的更新，例如线段树，但这里有更简单的做法。

因为 DP 数组一次都是更新一段区间，因此将有很多值相同。类比珂朵莉树，我们使用 map 维护一个取值相同区间的左端点。也就是 y 坐标上的 DP 值 +1 时，就在 map 中记录一下。此时 map 维护的是一个键、值都单调递增的序列。要知道 dp[y] 的值，可以通过在 map 内找到第一个小于等于 y 的键对应的值得到。