自己写的… 515ms
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
ll s[N];
vector<int> nums[N];
priority_queue<int> heap;
PII interval[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = a[i] + s[i - 1], heap.push(a[i]);
scanf("%d", &m);
ll pre_sum = 0;
int l, r;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &l, &r);
interval[i] = {l, r};
pre_sum += s[r] - s[l - 1];
b[l] += 1, b[r + 1] -= 1;
}
l = N, r = 0;
for (int i = 1; i <= n; i++) {
b[i] += b[i - 1];
l = min(l, b[i]), r = max(r, b[i]);
nums[b[i]].push_back(i);
}
for (int i = r; i >= l; i--)
for (auto x : nums[i])
a[x] = heap.top(), heap.pop();
for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];
ll sum = 0;
for (int i = 1; i <= m; i++) {
l = interval[i].x, r = interval[i].y;
sum += s[r] - s[l - 1];
}
printf("%lld", sum - pre_sum);
return 0;
}
y总的思路… 241ms
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
int a[N], s[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
int l, r;
while (m--) {
scanf("%d%d", &l, &r);
s[l]++, s[r + 1]--;
}
for (int i = 1; i <= n; i++) s[i] += s[i - 1];
ll pre_sum = 0;
for (int i = 1; i <= n; i++)
pre_sum += (ll)a[i] * s[i];
sort(a + 1, a + 1 + n);
sort(s + 1, s + 1 + n);
ll sum = 0;
for (int i = 1; i <= n; i++)
sum += (ll)a[i] * s[i];
printf("%lld", sum - pre_sum);
return 0;
}