代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
long long w[1000005];
int t1,t2;
long long ans;
struct item{
    int from,id;
}c[1000005];
int buc[2000005];
int l=0;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main(){
    n=1e6;m=1e6;
    ans=(1ll*(1+n)*n/2)*m;
    for(int i=0;i<2000005;++i)buc[i]=-1;
    for(int i=0;i<n;++i)a[i]=rand()%1000000;
    sort(a,a+n);
    for(int k=0;k<m;++k){
        t1=1e6/m;
        while(t1--){
            t2=rand();
            buc[t2]=k;
        }
    }
    int j=0;
    for(int i=0;i<n;++i){
        while(j<a[i]){
            if(buc[j]!=-1)
                w[buc[j]]+=1ll*(n-i);
            ++j;
        }
    }
    sort(w,w+m);
    for(int i=0;i<m;++i){
        ans+=(m-i)*w[i];
    }
    printf("%lld\n",ans);
}

评测结果