区間 \([l,r]\) を二次元平面上に移して考えます。区間 \(i\) と交差する \((l,r)\) は \(L_i < l < R_i < r\) または \(l < L_i < r < R_i\) を満たし、これはそれぞれ矩形領域になり、またこの二つの領域は重なりません。したがって、すべての区間に対して交差する \((l,r)\) の領域を求め、最も多くの領域が重なる場所を探せばよいです。

ここからは ABC346-G Alone の公式解説 と同様の言い換えを行っています。

よって、以下の問題を解ければよいことがわかります。

整数の組 \((x_i,y_i,z_i,w_i)\) が \(N\) 個与えられる。 \(x_i \leq L \leq y_i, z_i \leq R \leq w_i\) を満たす \(i\) の個数が最大となる \((L,R)\) を求めよ。

また、この問題を以下のように言い換えることができます。

最初に全ての要素が \(0\) の \(2\) 次元配列 \(A\) があり、\(N\) 個の整数の組 \((x_i,y_i,z_i,w_i)\) が与えられる。各 \(i\) について、 \(x_i \leq l \leq y_i, z_i \leq r \leq w_i\) を満たす \((l,r)\) に対して \(A_{l,r}\) を \(1\) 増やす。最終的に \(A\) の最大値およびそれを達成する \((l,r)\) を求めよ。

この問題は以下のように平面走査をすることができます。

　最初にすべての要素が \(0\) の配列 \(C\) が与えられる。また、最大値を0で初期化する。 \(N\) 個の整数の組 \((x_i,y_i,z_i,w_i)\) が与えられ、\(l=0,\ldots 10^9\) の順で以下の操作を行う

• \(x_j=l\) を満たす整数の組 \((x_j,y_j,z_j,w_j)\) について、\(z_j \leq r \leq w_j\) を満たす \(r\) に対して \(C_r\) を \(1\) 加算する。
• \(C\) の最大値を取得し、最大値が更新される場合はその時の \(l\) と最大値を達成する最小の \(r\) を記録する。
• \(y_j=l\) を満たす整数の組 \((x_j,y_j,z_j,w_j)\) について、\(z_j \leq r \leq w_j\) を満たす \(r\) に対して \(C_r\) を \(-1\) 加算する。

この問題のままだと \(l\) や \(r\) としてありえる値が多いですが、適切に座標圧縮することでそれぞれ \(O(N)\) 個に限定することが可能です。具体的には \(l\) は \(L_i+1\) や \(R_i-1\) などを取り得ます。また、\(r\) は \(L_i+1\) や \(R_i-1\) や \(R_i+1\) などを取り得ます。

これを愚直に行なうと 計算量が \(O(N^2)\) になってしまいますが、区間 Add 区間 Max のLazy Segment Tree を用いることによって \(O(N\log N)\) で解くことができます。

また、実装の際には \(f(l,r)\) の最大値が \(0\) であるときの答えが必ず \(l=0,r=1\) であることに注意してください。

詳細は実装例を参照してください。

実装例(C++)