平面走査(法) (scanline algorithm?)

• 上記画像は https://atcoder.jp/contests/abc174/tasks/abc174_f の解説放送から
• 2Dにプロットしてそれぞれ処理していくのだが、処理順をx軸またはy軸の順に滑らせる
• BIT, segtreeがお供？

問題集

• Range Set Query
  • https://atcoder.jp/contests/abc174/tasks/abc174_f
  • [l,r]のユニークな種類数を求めよ
• PAST2 N-ビルの建設
  • https://atcoder.jp/contests/past202004-open/tasks/past202004_n
  • 公式解説に平面走査の記述あり
  • 座標圧縮がお供

クエリと状態変化を同列で扱ってt順に処理

• PAST5 N-旅行会社/Travel Agency
  • https://atcoder.jp/contests/past202012-open/tasks/past202012_n
  • AC✅https://atcoder.jp/contests/past202012-open/submissions/25127731
  • 前提条件：クエリが先読みできる