Acwing-4655. 重新排序

我们可以累计每个 A[i] 的被求和次数 c[i]。容易贪心得到，被求和次数越多的肯定得放越大的数。

我们可以先统计原来的求和的总和 sum，再给 A 数组和统计求和次数的数组 c 从小到大排好序，最后依次相乘起来即 ∑(i=1~n) a[i]*c[i]减去原来的总和 sum 便是答案。

统计求和次数时注意到只有修改操作而没有查询操作，于是可以用差分来维护。具体地，我们建立一个都为0的差分数组b，当 l∼r 这段区间被求和时，就将 b[l] 加上1，b[r+1]减去1就可以了。

注意：原来的总和和最大总和都要用 long long 来存储。

时间复杂度：O(nlogn)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int w[N], s[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    
    scanf("%d", &m);
    while (m --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        s[l] ++, s[r + 1] --;
    }
    
    for (int i = 1; i <= n; ++ i)
        s[i] += s[i - 1];
        
    LL sum1 = 0;
    for (int i = 1; i <= n; ++ i)
        sum1 += (LL)s[i] * w[i];
        
    LL sum2 = 0;
    sort(s + 1, s + n + 1);
    sort(w + 1, w + n + 1);
    for (int i = 1; i <= n; ++ i)
        sum2 += (LL)s[i] * w[i];
        
    printf("%lld\n", sum2 - sum1);
    return 0;
}