セグメント木コンテストのＤ問題の解説

yukicoder_878.txt

yukicoder No. 878 解説

・問題文
No.878 Range High-Element Query - yukicoder
https://yukicoder.me/problems/no/878

・記号
next[i] := min{ k | k > i かつ a[k] > a[i] }
prev[i] := max{ k | k < i かつ a[k] > a[i] }
（ただし a[0] = a[N+1] = ∞ とする）

・解法
普通のセグ木を２つ（sum と arg_max）使う。
まず prev を求める。これは a を後ろから順にスタックに入れながら見て行けば線形時間で可能。
そして b[i] := 1 - #{ j | prev[j] = i } とすると、この b は「任意の i に対し sum b[i, next[i]) = 1」という性質を持つ（証明は後述）。
そのため r' := arg_max a[l, r] とすれば、クエリ [l, r] への答えは sum b[l, r') + 1 となる。

・sum b[i, next[i]) = 1 の証明：
各 i に対し、i から prev[i] への辺を張ったグラフを考えると、b[i] はこのグラフの i の「出次数 - 入次数」である。
次数を [i, next[i]) 全体で考えると、ここへ入る辺はなく、出る辺は i → prev[i] だけなので、sum = 1 となる。（証明終）