AcWing 4655. 重新排序
原题链接
中等
作者:
和和弦
,
2024-03-05 15:17:37
,
所有人可见
,
阅读 25
#include<iostream>
#include<algorithm>
using namespace std;
using i64 = long long;
const int N = 1e5 + 10;
int a[N];
i64 sum[N];
int whole[N], b[N];
bool cmp(int x, int y){
return x > y;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum[i] = a[i] + sum[i - 1];
}
int m; cin >> m;
i64 fin = 0;
while(m--){
int l, r; cin >> l >> r;
fin -= sum[r] - sum[l - 1];
b[l]++; b[r + 1]--;
}
for(int i = 1; i <= n; i++)
whole[i] = b[i] + whole[i - 1];
sort(whole + 1, whole + n + 1, cmp);
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++)
fin += 1LL * a[i] * whole[i];
cout << fin << endl;
return 0;
}