题意简述
给你数轴上的 $n$ 个线段，第 $i$ 个线段表示为 $[l_i, r_i]$。初始时，所有线段都未被标记。
重复进行以下操作，直到没有未标记的线段：
在第 $k$ 次操作中，如果至少还有两个未标记的线段，选择任意两个未标记的线段 $[l_i, r_i]$ 和 $[l_j, r_j]$，将它们标记，并添加一个新的已标记线段 $[x_k, y_k]$，满足以下条件：
$l_i \le x_k \le r_i$
$l_j \le y_k \le r_j$
$x_k \le y_k$
如果只剩下一个未标记的线段，将其标记。
你的任务是确定在过程结束时，所有已标记线段的最大可能总长度。线段 $[l, r]$ 的长度为 $r-l$。
思路分析
首先，所有的线段最终都会被标记，所以答案里面一定会有一个 $\sum\limits_{i=1}^n (r_i-l_i)$。
所以实际上能操作的部分就是 $[x_k,y_k]$ 了。
而每一组被标记的线段，都是一条取左端点，一条取右端点，才能得到最长的新线段。
放到总体里面就是，$\sum\limits{i=1}^{\lfloor\tfrac{n}{2}\rfloor} r_i - \sum\limits{j=1}^{\lfloor\tfrac{n}{2}\rfloor} l_j$，即一半线段取左端点，一半线段取右端点。
那么怎么取呢？
假设我们先全部都取右端点，那这部分的总代价就是 $\sum\limits_{i=1}^n r_i$.
然后我们选择 $\lfloor\dfrac{n}{2}\rfloor$ 条线段，改选左端点。改选线段 $i$ 会导致总代价减少 $l_i + r_i$.
我们要使总代价最小，那么就要取 $l_i + r_i$ 最小的 $\lfloor\dfrac{n}{2}\rfloor$ 条线段进行修改。
所以如果我们将所有线段按照 $l_i + r_i$ 排序，我们最终的答案就会是左边的 $\lfloor\dfrac{n}{2}\rfloor$ 根线段取左端点，右边的 $\lfloor\dfrac{n}{2}\rfloor$ 根线段取右端点。
如果 $n$ 是偶数，那么这个策略就足够了。
如果 $n$ 是奇数，那么还会剩下来一根线段。
剩下来哪根并不确定。我们枚举每一根被剩下来的情况。
我们没有必要每次枚举都重新计算代价。这样这部分的复杂度是 $O(n^2)$，会超时。
注意到每次枚举都可以由初始状态转移过来。
我们首先令最中间的线段被剩下来。
我们计算前 $\lfloor\dfrac{n}{2}\rfloor$ 根线段的左端点的和 $\text{sum}_l$ 和 后 $\lfloor\dfrac{n}{2}\rfloor$ 根线段的右端点的和 $\text{sum}_r$。
记中间值 $k = \lfloor\dfrac{n}{2}\rfloor + 1$.
假设我们枚举到第 $i$ 根线段，那它对应的代价就是：
- 如果 $i \lt \lfloor\dfrac{n}{2}\rfloor$，说明是前半段的不要了，用中间那根线段替代。代价为 $(\text{sum}_l-l_i+l_k) + \text{sum}_r$
- 如果 $i \gt \lfloor\dfrac{n}{2}\rfloor$，说明是后半段的不要了，用中间那根线段代替。代价为 $\text{sum}_l + (\text{sum}_r-r_i+r_k)$
所有情况取最大值。