ABL D. Flat Subsequence

問題

整数列A_iと整数Kが与えられる。
以下の条件を満たす数列Bの長さとして考えられる最大値を答えよ。

• BはAの(連続とは限らない)部分列
• どのBの隣り合う要素の差の絶対値もK以下

制約

• 1 <= N, A_i, K <= 3 * 10^5

解法

セグメント木に「その値が最後になる部分列の最長の長さ」をもたせる。
すると、A_iに対して、「A_i-KからA_i+Kの範囲での最大値+1」が最長の長さになる。
これをA_iに対して更新していき、最後に全範囲での最大値を答えればよい。

反省

「各要素から次に選べる要素に辺をはったグラフにおける最長路」を考えようとして、そのままだと辺数が多すぎるので「各要素から、その要素以降で次に選べる要素の中で一番indexが近いものに辺をはる」とやってしまった。

が、これは嘘解法で、

6 5
10 10 5 11 12 13

みたいなケースで、「10 10 5」を選んでしまう。
(正しくは「10 10 11 12 13」)