蓝桥2128 重新排序（差分）

给定一个数组A和一些查询Li和Ri，求数组第Li个至第Ri个元素之和。 小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

大致思路：m次查询，每次求Li至Ri之和，我们可以用差分统计每个位置被加多少次数，由贪心可知，次数多的位置放的数要尽可能大，按照这个要求排序就可以统计答案，减去原来的答案就是增加了多少。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], s[N], c[N], ans1, ans2;
pair<int, int> q[N], b[N];
bool cmp1(int x, int y) {
    return x > y;
}
bool cmp2(pair<int, int> x, pair<int, int> y) {
    return x.first > y.first;
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] = a[i] + s[i - 1];
    }
    cin >> m;
    for (int i = 1; i <= m; i ++) {
        int l, r; cin >> l >> r;
        q[i].first = l, q[i].second = r;
        b[l].first ++, b[r + 1].first --;
        ans1 += s[r] - s[l - 1];//统计最初的答案 
    }
    memset(s, 0, sizeof(s));
    for (int i = 1; i <= n; i ++) {
        b[i].second = i;
        b[i].first += b[i - 1].first;
    }
    sort(a + 1, a + n + 1, cmp1);
    sort(b + 1, b + n + 1, cmp2);
    for (int i = 1; i <= n; i ++) c[b[i].second] = a[i];
    for (int i = 1; i <= n; i ++) s[i] = c[i] + s[i - 1];
    for (int i = 1; i <= m; i ++) {
        int x = q[i].first, y = q[i].second;
        ans2 += s[y] - s[x - 1];//统计最优答案 
    }
    cout << ans2 - ans1 << '\n';
    return 0;
}