CSAcademy Round #26 (Div. 2 only) E. Critical Cells

リンク
https://csacademy.com/contest/archive/task/critical-cells/

問題概要

$N*M$ のグリッド上に $K$ 個の特別なセルが存在する。
いま $(1, 1)$ から $(N, M)$ まで右方向と下方向のみを使って移動するとき、できるだけ多くの特別なセルを経由したい。

次の状態を満たすような特別なセルを $Best$ と定義する。
ある任意の特別なセルを1つ選んで削除したとき、特別なセルの最大経由数が小さくなる。

このとき $Best$ な特別なセルの個数を求めよ。

制約

$1 \leq N, M \leq 10^9$
$1 \leq K \leq 10^5$

解法

まずセルを削除しない場合の最大経由数を求める。
下と右方向にしかできないことから、 $(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)$ のような列を考えたとき、 $x_i \leq x_j$ 及び $y_i \leq y_j$ を満たせばよい。
これはx軸方向にソートしたときのy軸方向についての広義単調増加列（LIS）に一致する。

次にLISに含まれる候補が複数ある場合、特別なセルを削除しても最大経由数が変化しない場合があるためどの点がLISの候補なのかを求める。
LISの長さは逆順から見たときの広義単調減少列（LDS）の長さに一致することから、先頭と後ろからLIS（LDS）を求めて、 $i$ について $l_i+r_i-1$ がLISの長さに一致するならば、候補に含まれることが言える。