競技プログラミング用 知識集積所
ABC424F - Adding Chords
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
円環であることはあまり意味がないので、円を切り開いて、点1から点Nまでが一直線に並んでいるとして考える。
そして、点aと点bを結ぶことを、a<=x<=bの区間を┏━━━┓状の線で覆うと考える。
これでも線の高さをうまくとる（長いほど高くとる）前提でなら、問題は変わらない。
そして、点aと点bを結ぶことを、a<=x<=bの区間を┏━━━┓状の線で覆うと考える。
これでも線の高さをうまくとる（長いほど高くとる）前提でなら、問題は変わらない。
ここで、2つの隣接する点の上に何本横線が引かれるかを被覆数として考える。
既存の線に交差がない前提なら、引きたい線の交差本数は、新しく線を引きたい区間での「左端の被覆数+右端の被覆数-2*被覆数最小値」で求められる（ABC405F参照）。
特に、それが0であるかは、左端の被覆数、右側の被覆数、被覆数最小値が全て一致するかどうかで判定できる。
例えば入力例1の場合、2つ目の入力は、2-3の区間は被覆数1、6-7間の被覆数0なので、2-7間の最少被覆数0に両方一致にはなっておらず、1+0-2*0=1本交差している。
既存の線に交差がない前提なら、引きたい線の交差本数は、新しく線を引きたい区間での「左端の被覆数+右端の被覆数-2*被覆数最小値」で求められる（ABC405F参照）。
特に、それが0であるかは、左端の被覆数、右側の被覆数、被覆数最小値が全て一致するかどうかで判定できる。
例えば入力例1の場合、2つ目の入力は、2-3の区間は被覆数1、6-7間の被覆数0なので、2-7間の最少被覆数0に両方一致にはなっておらず、1+0-2*0=1本交差している。
これを実装するには、以下の2つが必要。
- 新しく引いた線の被覆数処理のため、区間加算
- 被覆数最小値を出すため、区間最小値
これを高速に両方するには、lazy segment木※が最適である。
