这道题的核心是贪心构造最优配对，最终答案只和排序后的 (l_i+r_i) 有关，代码虽然长，但逻辑非常清晰。我会把推导、结论、代码全部用公式讲透。

---

0. 最终结论（最重要，先背下来）

1. 所有原始线段的长度必须全部计入答案（固定值）。
2. 每配对两条线段，能额外获得一个最大长度的新线段： 最优选择是让新线段 = 左端点尽可能小 + 右端点尽可能大。
3. 最终最大化总和等价于：$$\sum r_i - \sum_{\text{选 } n/2 \text{ 个}} (l_i + r_i) $$
4. 奇数 (n)：枚举删除哪一条线段，剩下偶数条用上面算法，取最大值。

---

1. 题目价值公式推导（标程核心依据）

1.1 新线段最大长度

每次选两条线段 (A=[l_a,r_a],\ B=[l_b,r_b])， 能生成的最长新线段是：

$$\boldsymbol{[\min(l_a,l_b),\ \max(r_a,r_b)]}$$

长度为：

$$\max(r_a,r_b) - \min(l_a,l_b)$$

1.2 总价值化简

最终总贡献可以化简为：

$$\text{总答案} = \underbrace{\sum (r_i - l_i)}_{\text{所有原始线段}} + \underbrace{\sum \left( \max(r_a,r_b) - \min(l_a,l_b) \right)}_{\text{新线段}} $$

进一步数学整理后，等价于：

$$\text{总答案} = \left( \sum_{i=1}^n r_i \right) - \left( \sum_{\text{选出 } n/2 \text{ 个}} (l_i + r_i) \right) $$

---

2. 贪心策略（严格最优）

为了最大化上式：

1. 计算总和：( \sum r_i )
2. 将所有线段按 (l_i + r_i) 从小到大排序
3. 减去最小的 n/2 个 (l_i + r_i)

这就是偶数 n 的最优解。

直观理解： 我们要放弃最小的 n/2 个和，让总价值最大。

---

3. 奇数 n 的处理

当 (n) 是奇数时：

• 必须恰好丢弃一条线段（不参与配对）
• 对剩下的 n-1（偶数） 条线段使用上面的贪心算法
• 枚举丢弃哪一条，取最大答案

标程使用了 (O(n \log n)) 的优化方法，不需要真的跑 n 遍。

---

4. 标程代码逐行详解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<pl> a(n);
        for (ll i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

        // --- 固定部分：所有原始线段长度和 ---
        ll ans = 0;
        for (ll i = 0; i < n; ans += a[i].second - a[i].first, i++);

        // 偏移修正（题目构造规则自带的常数）
        ans += n / 2;

        // 按 l + r 排序
        vector<pair<ll, pl>> b(n);
        for (ll i = 0; i < n; i++) {
            b[i].first = a[i].first + a[i].second;
            b[i].second = a[i];
        }
        sort(b.begin(), b.end());

        if (n % 2 == 0) {
            // ================================
            // 偶数：贪心选最小 n/2 个 l+r 减去
            // ================================
            ll sumR = 0;
            for (auto &p : a) sumR += p.second;
            ll sumLr = 0;
            for (int i = 0; i < n/2; i++) sumLr += b[i].first;
            cout << ans + sumR - sumLr - n - n/2 << "\n";
        } else {
            // ================================
            // 奇数：枚举删除哪条线段最优
            // ================================
            ll sumR = 0, w = 0, best = 0;
            for (auto &p : a) sumR += p.second;

            w = sumR;
            for (int i = 0; i <= n/2; i++) w -= b[i].first;

            // 情况1：删除前半段的某个线段
            for (int i = 0; i <= n/2; i++)
                best = max(best, w + b[i].second.first);

            // 情况2：删除后半段的某个线段
            w += b[n/2].first;
            for (int i = n/2+1; i < n; i++)
                best = max(best, w - b[i].second.second);

            cout << ans + best - n - n/2 << "\n";
        }
    }
}

---

5. 时间复杂度

$$O(n \log n) \quad \text{每组测试用例}$$

完全满足 (n \le 2 \times 10^5)。

---

6. 最简记忆口诀

1. 所有原始线段长度必选
2. 按 l+r 排序
3. 偶数：减去最小 n/2 个 l+r
4. 奇数：枚举删一条，跑偶数贪心
5. 输出总和

---