Range MinPair Query

2 secs 1024 MB
Nachia

次のようなセグメント木を用いて解けます。

  • セグメント木の各ノードでは つの値をもつ。順番に と呼ぶことにする。
  • はそのノードに対応する区間における の最小値である。
  • はそのノードに対応する区間における の最小値である。
  • はそのノードに対応する区間に対するクエリの答えである。

計算量は です。