前言

看了大家的做法，什么冒泡排序，插入排序，树状数组，线段树,都好厉害呐，我都没想出来

但我发现竟然还没有人用主席树，于是我跟大家交流一下 主席树 做法

显然我们有

\(Ans=\sum_{i=1}^n\sum_{j=1}^{i-1}a_j\geq{}a_i\)

于是这样用主席树做

考虑每个\(i\)对\(Ans\)的贡献，发现只需要统计出大于\(a_i\)的数的个数，注意这些数应该是已经出现了的

用主席树维护答案，查询\(0\to{}i-1\)的历史版本，做法已经很明确了

最后分析时间复杂度

对每个\(i\)我们要先查询\([a_i+1,n]\)数的个数，需要\(O(\log_2n)\)时间，然后插入这个数也需要\(O(\log_2n)\)时间

因此总时间复杂度为\(O(n\log_2n)\)

放代码

#include<iostream>#include<cstring>using namespace std;const int maxn=1e4+7;struct PreSegTree{    int sum;    int L,R;}PST[maxn*16];int root[maxn],cnt;void insert(int&now,int l,int r,int x){    PST[++cnt]=PST[now];    now=cnt;    ++PST[now].sum;    if(l==r) return;    int mid=(l+r)>>1;    if(x<=mid)        insert(PST[now].L,l,mid,x);    else if(x>=mid+1)        insert(PST[now].R,mid+1,r,x);}int query(int i,int j,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr)        return PST[j].sum-PST[i].sum;    int mid=(l+r)>>1;    int ans=0;    if(ql<=mid)        ans+=query(PST[i].L,PST[j].L,l,mid,ql,qr);    if(qr>=mid+1)        ans+=query(PST[i].R,PST[j].R,mid+1,r,ql,qr);    return ans;}int main(){    memset(PST,0,sizeof(PST));    memset(root,0,sizeof(root));    cnt=0;    int n;    cin>>n;    int a,ans=0;    for(int i=1;i<=n;++i)    {        cin>>a;        if(a<n) // 注意a==n时统计要特判掉            ans+=query(root[0],root[i-1],1,n,a+1,n);        root[i]=root[i-1];        insert(root[i],1,n,a);    }    cout<<ans<<endl;}