西北工业大学“编程之星”程序设计挑战赛 A 张经理的员工

解法：

时间复杂度：

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 100005;
int a[maxn] , b[maxn];
ll pre[maxn] , fpre[maxn];
ll cpre[maxn] , cfpre[maxn];
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    ll sum = 0,sum2 = 0;
    for(int i=1;i<=100000;i++){
        if(b[i]){
            sum += 1ll*i*b[i];
            sum2 += 1ll*b[i];
        }
        pre[i] = sum; 
        cpre[i] = sum2;
    }
    sum = 0,sum2 = 0;
    for(int i=100000;i>=1;i--){
        if(b[i]){
            sum += 1ll*i*b[i];
            sum2 += 1ll*b[i];
        }
        fpre[i] = sum;
        cfpre[i] = sum2;
    }
    while(q--){
        int l,r;
        ll ans = 0;
        scanf("%d %d",&l,&r);
        if(l > r)
            swap(l , r);
        ll x = 1ll*cpre[l]*l - 1ll*pre[l];
        ll y = 1ll*fpre[r] - 1ll*cfpre[r]*r;
        ll z = 0 , w = 0;
        if(r - l > 1){
            int x = r - l;
            int l2 = l + x/2;
            z = pre[l2] - pre[l] - (cpre[l2] - cpre[l])*l;
            int r2 = l2;
            w = r*(cpre[r-1] -  cpre[r2]) - (pre[r-1] - pre[r2]);
        }
        cout<<x + y + z + w<<endl;
    } 
     return 0;
}