A Cruel Segment's Thesis

The original segments are all marked eventually. No exceptions, no clever loophole. So this part is fixed:

$$\text{base}=\sum_{i=1}^{n}(r_i-l_i).$$

The only thing we can optimize is the sum of lengths of the new marked segments created when we pair two original segments.

For two segments $[l_i,r_i]$ and $[l_j,r_j]$, we can choose one point from one segment and one point from the other. To maximize the length, we obviously take the smallest available left point and the largest available right point. Therefore the best extra length of this pair is

$$\max(r_i,r_j)-\min(l_i,l_j).$$

So the problem becomes: pair up $2\lfloor n/2\rfloor$ segments, possibly leaving one unused if $n$ is odd, to maximize the sum of bounding interval lengths of the pairs.

Turn Pairs Into Roles

In every pair, one segment donates the left endpoint, and one segment donates the right endpoint.

If segment $i$ is a left donor, it contributes $-l_i$. If segment $i$ is a right donor, it contributes $+r_i$.

Let

$$m=\left\lfloor \frac n2 \right\rfloor.$$

We need exactly $m$ left donors and exactly $m$ right donors, all distinct, maximizing

$$\sum_{i\in R} r_i-\sum_{i\in L} l_i.$$

Then the final answer is

$$\text{base}+\sum_{i\in R} r_i-\sum_{i\in L} l_i.$$

The remaining question is: which segments should be left donors and which should be right donors?

The Key Swap Argument

Suppose segment $a$ is currently a right donor and segment $b$ is currently a left donor. Their contribution is

$$r_a-l_b.$$

If we swap their roles, the contribution becomes

$$r_b-l_a.$$

Swapping is at least as good when

$$r_b-l_a \ge r_a-l_b.$$

Rearrange it:

$$l_a+r_a \le l_b+r_b.$$

So if $a$ has smaller $l+r$ than $b$, then $a$ should not be the right donor while $b$ is the left donor. Swap them and the answer does not get worse.

That gives the structure of an optimal solution:

After sorting segments by $l_i+r_i$, all left donors can be placed before all right donors.

That is the whole trick. The problem looks like pairing chaos, but it collapses into one sorted order.

Choosing Across a Split

Sort segments by $l_i+r_i$.

For some split position $i$:

• left donors are chosen from the prefix $[0,i)$;
• right donors are chosen from the suffix $[i,n)$.

We need choose exactly $m$ left donors and $m$ right donors.

For the prefix, to maximize $-\sum l_i$, choose the $m$ smallest $l_i$ values.

For the suffix, to maximize $\sum r_i$, choose the $m$ largest $r_i$ values.

So we precompute:

• pref[i] = best value of $-\sum l$ by choosing $m$ segments from the first $i$ segments;
• suf[i] = best value of $\sum r$ by choosing $m$ segments from segments $i$ through $n-1$.

Then the best extra contribution is

$$\max_{0\le i\le n}(pref[i]+suf[i]).$$

This also handles odd $n$ naturally: one segment may sit between the chosen prefix donors and suffix donors, effectively unused for the extra pair score.

Maintaining the Best Prefix/Suffix Values

For pref, sweep left to right and keep the $m$ smallest $l$ values seen so far. Use a max-heap. If the heap gets bigger than $m$, remove the largest $l$.

For suf, sweep right to left and keep the $m$ largest $r$ values seen so far. Use a min-heap. If the heap gets bigger than $m$, remove the smallest $r$.

Each heap operation costs $O(\log n)$, so the whole solution is

$$O(n\log n)$$

per test case, with total $n\le 2\cdot 10^5$. Fits easily.