https://atcoder.jp/contests/abc339/tasks/abc339_e
概要
数列 $A$ が与えられる。$A$ の部分列でありながら隣接する値の差が $D$ 以下であるようなものの最長の長さを答えろ。
結論から言うと作用が $\mathrm{max}$ のSegment Treeを使う。
Segment Treeを配列そのまま突っ込むような使い方ではなく添字を値として考える。(BITで転倒数を求めるような使い方をする)
この問題は$A$ を前から見ていったときに $A[i] \pm D$ の範囲の中で $\mathrm{max}$ を取った値を $A[i]$ に $1$ 足して代入すればよい。
Segment Treeの一番下の部分だけを図式すると以下のようになる。
$A[i]$ をみたときに $A[i]$ 以前に隣接する値の差が $D$ 以下になるような数が何個あるかを知ることができればよい。
そのためにSegment Treeを用いて区間 $\mathrm{max}$ を求めて $A[i]$ にその値 $+1$ するということを最後まで繰り返したあと、Segment Treeの全ての区間の $\mathrm{max}$ を求めてあげれば答えが求まる。
提出