ABC360-F InterSections

ABC360-F InterSections（Difficulty: 2563）の解説です．

問題

両端が整数である $N$ 個の閉区間 $\left[L_i, R_i\right]\ \left(1\leq i\leq N\right)$ が与えられる．$0\leq l<r\leq10^9$ を満たす整数の組 $(l, r)$ であって，$N$ 個の閉区間のうち区間$\left[l,r\right]$と交差するものの個数が最大となるものを求めよ．複数ある場合，$l$ が最小となるもののうち $r$ が最小となるものを求めよ．

ただし区間 $\left[l_a,r_a\right]$ と区間 $\left[l_b,r_b\right]$ が交差するとは，$l_a<l_b<r_a<r_b$ または $l_b<l_a<r_b<r_a$ が成立することを言う．

制約

• $1\leq N\leq10^5$
• $0\leq L_i<R_i\leq10^9\ \left(1\leq i\leq N\right)$

解答

区間 $\left[l,r\right]$ と区間 $\left[L_i,R_i\right]$ が交差する条件は，$(l, r)\in\left[0, L_i-1\right]\times\left[L_i+1, R_i-1\right]\sqcup\left[L_i+1, R_i-1\right]\times\left[R_i+1, 10^9\right]$ と書けます．

右辺は $2$ つの長方形領域の和集合（特に非交和）となります．したがって，$2$ 次元平面上で最も多くの長方形が重なる位置を求める問題になります．

これを平面走査で解きます．具体的には，直線 $x=l$ 上で最も多くの長方形が重なる位置を求めることを$l$ の昇順に繰り返します．各 $r$ にいくつの長方形が重なっているかは，適当な座標圧縮をしたうえで，区間最大値取得・区間加算クエリを処理するセグメントツリーで管理すればよいです．

各 $i$ に対し，区間加算クエリは以下のようにします：

• $l=0$ の直前に，$\left[L_i+1, R_i\right)$ に $1$ 加算
• $l=L_i$ の直前に，$\left[L_i+1, R_i\right)$ に $-1$ 加算
• $l=L_i+1$ の直前に，$\left[R_i+1, 10^9+1\right)$ に $1$ 加算
• $l=R_i$ の直前に，$\left[R_i+1, 10^9+1\right)$ に $-1$ 加算

時間計算量は $\mathrm{O}\left(N\log N\right)$ です．

実装例（C++, 950 ms）