Solution - Atcoder ABC177F I hate Shortest Path Problem

考虑按题目所述的进行 DP。
设计状态 \(f_{i, j}\) 代表强制要求 \((i, j)\) 要走向 \((i + 1, j)\) 最小的横坐标之差，这是因为对应的纵坐标之差是确定的。

对于转移，考虑到对于 \(j\not \in [a_i, b_i]\)，直接从上面转移下来即可，即 \(f_{i, j}\leftarrow f_{i - 1, j}\)。
对于 \(j\in [a_i, b_i]\)，不能往下走，就只能考虑往右走到到 \(b_i + 1\) 处，即 \(f_{i, b_{i} + 1}\leftarrow f_{i - 1, j} + b_{i} + 1 - j\)，同时 \(f_{i, j}\) 因为不能走就变为 \(+\infty\)。

需要用个数据结构优化一下。
考虑用一个 map 存在当前 \(f_{i, j}\not = +\infty\) 的 \(j\) 和 \(f_{i, j}\)。
那么对于第一种转移什么都不会发生，对于第二种转移，直接暴力删除区间内的点向 \(f_{i, b_i + 1}\) 更新即可。
同时需要一个 multiset 存下不为 \(+ \infty\) 的 \(f_{i, j}\) 以查找最小值。

时间复杂度分析考虑均摊，最多删去 \(H + W\) 个点，复杂度 \(\mathcal{O}((H + W)\log W)\)。

#include<bits/stdc++.h>
int main() {
   int H, W;
   scanf("%d%d", &H, &W);
   std::map<int, int> S;
   std::multiset<int> D;
   for (int i = 1; i <= W; i++) S[i] = 0, D.insert(0);
   for (int i = 1; i <= H; i++) {
      int a, b; scanf("%d%d", &a, &b);
      auto it = S.lower_bound(a);
      int mn = 1e9, w;
      while (it != S.end() && (w = (*it).first) <= b) {
         mn = std::min(mn, b + 1 - w + (*it).second);
         D.erase(D.find((*it).second)), S.erase(it++);
      }
      if (b < W && mn < (int)1e9) {
         if (S.find(b + 1) != S.end()) {
            D.erase(D.find(S[b + 1]));
            D.insert(S[b + 1] = std::min(S[b + 1], mn));
         } else {
            D.insert(S[b + 1] = mn);
         }
      }
      printf("%d\n", D.empty() ? -1 : ((*D.begin()) + i));
   } 
   return 0;
}