-
考えたこと
- 範囲内に色ciが存在するかどうかを対数オーダーで判定できれば間に合う
- 二分探索
-
実装
- 7分で実装、提出、TLE
- あ、全然ダメだ、各色ごとN件につき対数オーダーで範囲内にあるかどうか判定できてもO(QNlogN)だ
-
改めて考察
- クエリの先読みして二次元の片方を時間軸にするか
- それでも最悪O(QN)か
- 玉の色の集合を2^nのブロックごとに作る
- 集合は全部で2N-1個
- logN回のマージで要求された区間の色の集合ができる
- しかし普通にやるとマージが重くて結局O(QN)
- マージが軽い二項ヒープを使う？
- クエリの先読みして二次元の片方を時間軸にするか
-
公式解説
- 区間クエリといえばセグメント木だが、マージが重い
- クエリの先読みして二次元の片方を時間軸にする
- 各時点での各色の「最も右の球の場所」をメンテする
- これがLより大きければ、範囲内にその色がある、定数オーダー
- しかしこれでもO(QN)
- 各色の「最も右の球の場所」をフェニック木に入れる
- 個数を数えることが範囲和で対数オーダー
- なるほど、ここがポイントか
- 多くのものと大小比較→フェニック木
-
3TLE
クエリがたくさん問題 from ABC174 ARC174F