ABC 401-500/ABC435E - Cover query - 競技プログラミング用 知識集積所

---

問題

ABC435E

必要知識

B以下レベルの内容は省略

• ランレングス圧縮※的な考え方
• 二分探索※

考え方

データを真面目にもつと、長さ10^9になるので用意するだけでTLE。
ということで、ランレングス圧縮※の考え方を流用し、白マスの範囲を(L,R)の形でset※にいれておく。

クエリが来たら、二分探索※で該当する区間をdeque※か何かに抜き出し（区間の途中から抜き出す場合、区間を分割する処理も忘れずに）、抜き出した部分の長さを白マスの個数から減算していけばよい。

set※の中のデータ数は、クエリごとに最大1個ずつしか増えず、大量に参照するときには一気に中身の数が減るため、「大量のデータを何度も何度も扱う」という状況にはならず、計算量の心配は全くいらない。

解答例

解答例

注意点

別解