MojaCoder
Playground
問題
問題を投稿
コンテスト
コンテストを作成
EN
JA
登録
サインイン
Range MinPair Query
2 secs
1024 MB
Nachia
Tweet
問題
提出
テストケース
解説
次のようなセグメント木を用いて解けます。
セグメント木の各ノードでは
3
3
3
つの値をもつ。順番に
A
m
i
n
,
B
m
i
n
,
X
A_{\mathrm{min}},B_{\mathrm{min}},X
A
min
,
B
min
,
X
と呼ぶことにする。
A
m
i
n
A_{\mathrm{min}}
A
min
はそのノードに対応する区間における
A
A
A
の最小値である。
B
m
i
n
B_{\mathrm{min}}
B
min
はそのノードに対応する区間における
B
B
B
の最小値である。
X
X
X
はそのノードに対応する区間に対するクエリの答えである。
計算量は
O
(
(
N
+
Q
)
log
N
)
O((N + Q) \log N)
O
((
N
+
Q
)
lo
g
N
)
です。