ABC174F

https://gyazo.com/d1e4ee6d9ee7b595405a406cf1c6fbe7

考えたこと

範囲内に色ciが存在するかどうかを対数オーダーで判定できれば間に合う

二分探索

実装

7分で実装、提出、TLE

あ、全然ダメだ、各色ごとN件につき対数オーダーで範囲内にあるかどうか判定できてもO(QNlogN)だ

改めて考察

それでも最悪O(QN)か

玉の色の集合を2^nのブロックごとに作る

集合は全部で2N-1個

logN回のマージで要求された区間の色の集合ができる

しかし普通にやるとマージが重くて結局O(QN)

公式解説

区間クエリといえばセグメント木だが、マージが重い

各時点での各色の「最も右の球の場所」をメンテする

これがLより大きければ、範囲内にその色がある、定数オーダー

しかしこれでもO(QN)

個数を数えることが範囲和で対数オーダー

なるほど、ここがポイントか

3TLE

ARC174F