其实不需要求出选择区间以后的数组的顺序，只需要知道哪个数字用几次就可以了（当然肯定是大的数字让它出现的次数最多）

给出区间选择以后可以用一个num来存所有区间出现的次数（比如说区间为1到3和2到4，那么num[1] = num[4] = 1,num[2] = num[3] = 2）这个操作用差分来解决，就可以得到出现的次数了，然后按照上面讲原理的就容易得到最大的区间总和了

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0)

int n, m;
const int N = 1e5 + 5;
int a[N], num[N];
int apref[N];
int numdif[N];
int sum1, sum2;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        apref[i] = apref[i - 1] + a[i];
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        sum1 += (apref[r] - apref[l - 1]);
        numdif[l]++;
        numdif[r + 1]--;
    }
    for(int i = 1;i<=n;i++)
    {
        num[i] = num[i-1] + numdif[i];
    }
    sort(num + 1, num + 1 + n);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        sum2 += (num[i] * a[i]);
    }
    cout << sum2 - sum1 << endl;
    return 0;
}