思路
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
LL s[N];
int b[N];
int n, m;
LL s1, s2;
int main()
{
cin >> 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];
cin >> m;
while (m -- )
{
int l = 0, r = 0;
scanf("%d%d", &l, &r);
s1 += (LL)s[r] - s[l - 1];
b[l] += 1, b[r + 1] -= 1;
}
for (int i = 1; i <= n; i ++ )
b[i] = b[i] + b[i - 1];
// for (int i = 1; i <= n; i ++ )
// cout << b[i] << ' ';
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = n; i >= 1; i -- )
{
s2 += (LL)a[i] * b[i];
if (b[i] == 0) break;
}
printf("%lld", s2 - s1);
return 0;
}