蓝桥杯2022年第十三届省赛真题-重新排序

解题思路:
前缀和和差分数组减少运算量
注意事项:
不要超时和使用long long
参考代码:

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>//strlen、strcmp 
#include <cmath>
#include <cstdlib>//malloc
#include <algorithm>
using namespace std;


#define max 100010
int n,a[max],m,l,r;
long long sum[max]={0};
int cnt[max]={0},diff[max]={0};
long long s1=0,s2=0;
int main() {
int i;
scanf("%d",&n);//数组总数
for(i = 1;i <= n;++i){
scanf("%d",&a[i]);
sum[i] = sum[i-1] + a[i];
}
scanf("%d",&m);
for(i = 1;i <= m;i++){
scanf("%d %d",&l,&r);
s1 += sum[r] - sum[l-1];
diff[l]++;
diff[r+1]--;
}
for(i = 1;i <= n;i++){
cnt[i] = cnt[i-1] + diff[i];
}
sort(a+1,a+1+n);
sort(cnt+1,cnt+1+n);
for(i = 1;i <= n;i++){
s2 += ((long long)1) * a[i] * cnt[i];
}
printf("%lld\n",s2-s1);




return 0;
}