概要

\(A\) と \(B\) をマージソートした列を \(C\) とします。このとき、各展示における美術品の列を考えると、まず \(A, B\) どちらかの中のある区間が並び、その後に \(C\) 内のある区間が並び、最後にまた \(A, B\) どちらかの中のある区間が並ぶ構造となっています。

境界を二分探索等で求め、 \(A, B, C\) それぞれについて Segment Tree や Sparse Table を作っておくことでクエリに高速に答えられます。尺取り法による前計算と Sparse Table でクエリあたり定数時間にもなります。

詳細や解答例

解説スライド

小課題 1 コード

小課題 2 コード

小課題 3 コード