We consider the problem by mapping segments \([l,r]\) onto the two-dimensional plane. Segments \((l,r)\) that intersects with segment \(i\) satisfy \(L_i < l < R_i < r\) or \(l < L_i < r < R_i\), which form disjoint rectangular regions. Thus, it is sufficient to find the region of \((l,r)\) that intersects with each segment, and find the place covered by the most number of regions.

Hereinafter we rephrase the problem in the same way as the official editorial of ABC346-G.

It turns out that solving the following is sufficient:

Given \(N\) tuples of integers \((x_i,y_i,z_i,w_i)\), find \((L,R)\) that maximizes the number of indices \(i\) with \(x_i \leq L \leq y_i, z_i \leq R \leq w_i\).

One can further rephrase the problem as follows:

There is a two-dimensional array \(A\) whose elements are initially \(0\), and \(N\) tuples of integers \((x_i,y_i,z_i,w_i)\). For each \(i\), increment \(A_{l,r}\) by one for each \((l,r)\) with \(x_i \leq l \leq y_i, z_i \leq r \leq w_i\). Find the maximum value of the resulting \(A\), and \((l,r)\) that maximizes it.

This can be solved with a search line algorithm as follows:

You are given an array \(C\) whose elements are initially \(0\). Initialize the maximum value with \(0\). Given \(N\) tuples of integers \((x_i,y_i,z_i,w_i)\), perform the following procedure for \(l=0,\ldots 10^9\) in order:

• For each tuple of integers \((x_j,y_j,z_j,w_j)\) such that \(x_j=l\), for each \(r\) with \(z_j \leq r \leq w_j\), increment \(C_r\) by \(1\).
• Retrieve the maximum value of \(C\). If the maximum value should be updated, record the current \(l\), and \(r\) that achieves the maximum.
• For each tuple of integers \((x_j,y_j,z_j,w_j)\) such that \(y_j=l\), for each \(r\) with \(z_j \leq r \leq w_j\), increment \(C_r\) by \(-1\).

This procedure takes many different values for \(l\) and \(r\), but by applying coordinate compression appropriately they can reduced to \(O(N)\). Specifically, \(l\) can take \(L_i+1\) or \(R_i-1\). Also, \(r\) can take \(L_i+1\), \(R_i-1\), or \(R_i+1\).

Performing it naively costs \(O(N^2)\) time, but using a segment-add segment-max lazy segment tree reduces it to \(O(N\log N)\).

When implementing, note that if the maximum value of \(f(l,r)\) is \(0\), the answer is always \(l=0,r=1\).

For more details, please refer to the sample code.

Sample code (C++)