C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

贪心 + 前缀和 + 差分

$让查询次数越多的位置放越大的数$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;

int n, m;
int w[N];
int cnt[N]; // 差分数组，记录查询次数

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    cin >> m;
    while (m --) {
        int l, r;
        cin >> l >> r;
        cnt[l] ++, cnt[r + 1] --;
    }

    for (int i = 1; i <= n; i ++)
        cnt[i] += cnt[i - 1];

    ll before = 0;
    for (int i = 1; i <= n; i ++)
        before += (ll)w[i] * cnt[i];

    sort (w + 1, w + n + 1);
    sort (cnt + 1, cnt + n + 1);

    ll after = 0;
    for (int i = 1; i <= n; i ++)
        after += (ll)w[i] * cnt[i];     

    cout << after - before; 
    return 0;
} 

$\small{分享：}$

$\large\color{red}{— > 算法-STL(C/C++)}$