MojaCoder
Playground
Problems
Post Problem
Contests
Create Contest
EN
JA
Sign up
Sign in
Range MinPair Query
2 secs
1024 MB
Nachia
Tweet
Problem
Submissions
Test cases
Editorial
次のようなセグメント木を用いて解けます。
セグメント木の各ノードでは
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
)
です。