差分+模拟
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
typedef long long LL;
int n,m;
int a[N];
LL s[N],tt[N];
PII b[N];
LL ans,res;
vector<PII> last;
void insert(int l,int r)
{
b[l].x ++;
b[r + 1].x --;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i],b[i].y = i,s[i] = s[i - 1] + a[i];
sort(a + 1,a + 1 + n);
cin >> m;
while(m--)
{
int l,r;
cin >> l >> r;
last.push_back({l,r});
insert(l,r);
ans += s[r] - s[l - 1];
}
for(int i = 1;i <= n;i++)
b[i].first += b[i - 1].first;
sort(b + 1,b + n + 1);
// for(int i = 1;i <= n;i++)
// cout << b[i].x << ' ' << b[i].y << endl;
vector<int> nums(n + 1);
int idx = 0;
for(int i = 1;i <= n;i++)
nums[b[i].y] = a[++idx];
// for(int i = 1;i <= n;i++)
// cout << nums[i] << ' ';
for(int i = 1;i <= n;i++)
tt[i] = tt[i - 1] + nums[i];
for(auto k : last)
res += tt[k.y] - tt[k.x - 1];
cout << res - ans << endl;
return 0;
}
差分+贪心(排序不等式)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n,m;
int a[N],c[N];
LL s[N];
LL sum1,sum2;
void insert(int l,int r)
{
c[l] ++;
c[r + 1] --;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i],s[i] = s[i - 1] + a[i];
cin >> m;
while(m--)
{
int l,r;
cin >> l >> r;
insert(l,r);
sum1 += s[r] - s[l - 1];
}
for(int i = 1;i <= n;i++)
c[i] += c[i - 1];
sort(a + 1,a + 1 + n);
sort(c + 1,c + 1 + n);
for(int i = 1;i <= n;i++)
sum2 += (LL)c[i] * a[i];
cout << sum2 - sum1<< endl;
return 0;
}