区間と区間がかぶる問題まとめ

【重要】面倒なので、区間の始点終点はすべて異なるとします。そうじゃない場合は適切にソートして順序付けとかしてやると大丈夫です。多分。

すでに区間がたくさんあって交差する回数を数えるやつ

No.743 Segments on a Polygon - yukicoder

1. 区間を(start, end)のペアで持ち、小さい順にソートする
2. 座標値が収まるようなセグ木を持ち、0で初期化
3. (Ai, Bi)の区間の総和をcntに加算して、Biに1加算
4. 最終的なcntの値が答え

すでに区間がたくさんあって、クエリが飛んでてきて指定された区間内にいくつ区間が入っているかを答える

多分一番楽？

1. 座標値が収まるような配列を用意し、(Ai, Bi)に対してインデックスAiをBiにセットする
2. (Pi, Qi)の間に区間がいくつ収まってるかカウントするときは配列のPi, Qiの範囲内でQi以下の要素の個数を数えます（セグ木とか使って）。

hama-du-competitive.hatenablog.com

ここにも永続セグ木を使うやつとかWaveletMatrixを使うやつなどが載ってます。

区間が動的に追加されていくやつ

無理じゃね？と思っている