segment Treeを使用してRMQをとく。
RMQとは
数列a_0,a_1,...a_nがあるとき次の二つの処理をO(log n)で行う。
s, tが与えられたとき、a_s, a_s+1, .... , a_tの最小値を求める
i, xが与えられたとき、a_iの値をxに変更する
SegmentTreeとは
www.slideshare.net
第２２回アルゴリズム勉強会資料 from Yuuki Ono
www.slideshare.net
このあたりの説明が秀逸
数列a_0,a_1,...a_nがあるとき次の二つの処理をO(log n)で行う。
s, tが与えられたとき、a_s, a_s+1, .... , a_tの最小値を求める
i, xが与えられたとき、a_iの値をxに変更する
www.slideshare.net
このあたりの説明が秀逸