时间复杂度O(N + NlogN)

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
int a[N];
LL s[N]; //前缀和
int cnt[N]; //cnt[i]表示i这个点被使用到多少次 差分数组
int n;
int m;
void insert(int a , int b){
    cnt[a]++;
    cnt[b + 1]--;
}
int main (){
    scanf ("%d" , &n);
    for (int i = 1;i <= n;i++) scanf ("%d" , &a[i]);
    for (int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];
    scanf ("%d" , &m);
    int l = 0;
    int r = 0;
    LL sum = 0;
    for (int i = 0;i < m;i++){
        scanf ("%d %d" , &l , &r);
        insert(l , r);
        sum += s[r] - s[l - 1];
    }
    //cout << sum;
    //对cnt求一遍前缀和 就可以得到每个数被用了多少次
    for (int i = 1;i <= n;i++) cnt[i] += cnt[i - 1];
    //那么m次查询的总和应该等于
    //cnt[1]*a[1] + cnt[2]*a[2] + cnt[3]*a[3] ···· + cnt[n]*a[n]
    //现在要通过对a数组重新排序使得这个式子最大
    //那么可以让a数组的最大值与cnt数组的最大值匹配
    //a数组的次大值与cnt数组的次大值匹配
    //那么这个式子一定最大(排序不等式)
    //cnt数组是升序 a数组也是升序的时候最大
    sort(cnt + 1, cnt + n + 1);
    sort(a + 1 , a + 1 + n);
    LL reversesum = 0;
    for (int i = 1;i <= n;i++){
        reversesum += (LL)cnt[i] * a[i];
    }
    cout << reversesum - sum << endl;

    return 0;
}
//证明：cnt数组是升序 a数组也是升序的时候最大
//假设cnt数组是升序的  a数组不是升序的
//那么a数组一定存在2个数a[i] > a[i + 1]
//假设对应的cnt[i] < cnt[i + 1]
//不交换的和为 a[i]*cnt[i] + a[i + 1]*cnt[i + 1]
//交换a的2个数后的和为
//a[i + 1] * cnt[i] + a[i]*cnt[i + 1]
//2个式子相减得
//a[i]*cnt[i] + a[i + 1]*cnt[i + 1] - a[i + 1] * cnt[i] - a[i]*cnt[i + 1]
//整理得
//a[i](cnt[i] - cnt[i+1]) + a[i + 1](cnt[i + 1] - cnt[i])
//(a[i] - a[i + 1])*(cnt[i] - cnt[i + 1])
//因为a[i] > a[i + 1] 
//所以a[i] - a[i + 1] > 0
//因为cnt[i] < cnt[i + 1]
//所以cnt[i] - cnt[i + 1] 小于0
//则原式子小于0
//所以有
//a[i]*cnt[i] + a[i + 1]*cnt[i + 1] < a[i + 1] * cnt[i] - a[i]*cnt[i + 1]
//所以对于任意的2个数，如果a[i] > a[i + 1]
//那么把这2个数交换后，和会变大
//所以可以得到a数组应该也是一个单调递增的数组