Range MinPair Query

2 secs 1024 MB
Nachia's icon Nachia

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

  • セグメント木の各ノードでは 33 つの値をもつ。順番に Amin,Bmin,XA_{\mathrm{min}},B_{\mathrm{min}},X と呼ぶことにする。
  • AminA_{\mathrm{min}} はそのノードに対応する区間における AA の最小値である。
  • BminB_{\mathrm{min}} はそのノードに対応する区間における BB の最小値である。
  • XX はそのノードに対応する区間に対するクエリの答えである。

計算量は O((N+Q)logN)O((N + Q) \log N) です。