差分与前缀和，时间复杂度O(nlogn)

解题思路:代码和注释已经很清晰了

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 100010

#define maxm 100010

typedef long long ll;

int n,a[maxn],m,l,r;

ll sum[maxn];//sum[i]是a[]的前i个元素之和

int num[maxn],chafen[maxn];//num[i]表示第i个元素被查询的次数。chafen[i]=num[i]-num[i-1],所以num[i]=chafen[1]+chafen[2]+...chafen[i];

ll ans1,ans2;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        sum[i]=sum[i-1]+a[i];

    }

    scanf("%d",&m);

    for(int i=1;i<=m;i++){

        scanf("%d%d",&l,&r);

        ans1+=sum[r]-sum[l-1];

        chafen[l]++;

        chafen[r+1]--;

    }

    for(int i=1;i<=n;i++){

        num[i]=num[i-1]+chafen[i];

    }

    sort(num+1,num+1+n);

    sort(a+1,a+1+n);

    for(int i=1;i<=n;i++){

        ans2+=1LL*num[i]*a[i];//int乘int可能越int界，所以乘个1LL

    }

    printf("%lld",ans2-ans1);

    //system("pause");

    return 0;

}