AcWing 4655. 重新排序 | 堆, 前缀和, 差分
原题链接
中等
作者:
KeChang
,
2024-03-02 09:19:22
,
所有人可见
,
阅读 27
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
using PII = pair <int, int>;
using LL = long long;
const int N = 1e5 + 10;
int n, m, a[N], l[N], r[N], g[N];
LL arr[N];
priority_queue <int, vector <int>, greater <int>> nums;
priority_queue <PII, vector <PII>, greater <PII>> heap;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
nums.push(a[i]);
}
cin >> m;
for(int i = 1; i <= m; ++i) {
cin >> l[i] >> r[i];
++g[l[i]], --g[r[i] + 1];
}
for(int i = 1; i <= n; ++i) {
g[i] += g[i - 1];
heap.push({g[i],i});
}
while(!nums.empty()) {
auto t = heap.top().y; heap.pop();
auto val = nums.top(); nums.pop();
arr[t] = val - a[t];
}
for(int i = 1; i <= n; ++i) arr[i] += arr[i - 1];
LL ans = 0;
for(int i = 1; i <= m; ++i)
ans += arr[r[i]] - arr[l[i] - 1];
cout << ans;
return 0;
}