贪心问题推式子场
C
无论B做什么操作，A都可以直接取消B的操作，所以B会结束游戏，实际上只操作一次。
考虑交换左右端点对答案的贡献是多少，会得到一个含ij的式子，对每个点取最优贡献，然后取最大值。
D
部分贡献是固定的，考虑如何计算新增的贡献。
对于偶数，只需要对所有r求和再减去l+r最小的n/2个值就是答案。
对于奇数，按照偶数做以后枚举不选的区间求最大值。
直接找不选哪个区间我不会。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
// #define int long long
#define endl '\n'
#define pii pair<int, int>
#define ls(x) (x << 1)#define rs(x) (x << 1 | 1)
const int N = 2e5 + 7;
int n, m;
pii a[N];
void solve() {cin >> n;vector<pair<int, pii>> b(n + 1);ll ans = 0;ll w = 0, k = 0;for (int i = 1; i <= n; i++) {cin >> a[i].first >> a[i].second;b[i].first = a[i].first + a[i].second;b[i].second = a[i];ans += a[i].second - a[i].first;w += a[i].second;} sort(b.begin(), b.end());for (int i = 1; i <= (n + 1) / 2; i++) w -= b[i].first;k = w;if (n % 2) {for (int i = 1; i < n / 2 + 1; i++) {k = max(k, w + b[i].second.first);}w += b[n / 2 + 1].first;for (int i = n / 2 + 1; i <= n; i++) {k = max(k, w - b[i].second.second);}}cout << ans + k << endl;
}
signed main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T = 1;cin >> T;// p10[0] = 1;// for (int i = 1; i < 10; i++) p10[i] = p10[i - 1] * 10;while(T--) {solve();}
}