ABC 401-500/ABC405F - Chord Crossing - 競技プログラミング用 知識集積所

---

問題

ABC405F

必要知識

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

• 階差数列（未作成）
• segment木（未作成）

考え方

愚直にやると計算量が全然足りない。
そこで、どうにか工夫をする。

まず、円環である意味はあまりないので、1と2*nの間で切断する。
すると、A-Bの線とC-Dの線が交わる必要十分条件は、CとDのどちらか1つだけがAとBの間にあることとなる。
つまり、あるC-Dの線に対して、CとDのどちらか一方のみをまたぐA-Bの線の本数を高速で数えればよい。

例えば最初に引いてある線が2-4、6-12、8-10の3本ある場合、

範囲	00	01	02	03	04	05	06	07	08	09	10	11	12	13
2-4
6-12
8-10
個数	0	0	1	1	1	0	1	1	2	2	2	1	1	0

というように各点をまたぐ線の本数を数えておく。
これは階差数列（未作成）として、A.at(i)番目に+1、B.at(i)+1番目に-1を集計して、最後にその累積和を取ることで実現できる。

先に引いてある線同士は交わっていないという制限から、CをまたぐがDをまたがない線は、「Cをまたぐ線の個数」から「CからDまでのまたぐ個数の最小値」を引けば求められる。
同様に、DをまたぐがCをまたがない線は、「Dをまたぐ線の個数」から「CからDまでのまたぐ個数の最小値」を引けば求められる。
つまり、各クエリに対する解答は「Cをまたぐ線の個数」と「Dをまたぐ線の個数」を足して「CからDまでのまたぐ個数の最小値」の2倍を引いたものとなる。

区間内の最小値を高速に求めるには、segment木（未作成）などを利用すればよい。

解答例

解答例

注意点

別解