@zzzc18 2017-09-07T11:46:06.000000Z 字数 951 阅读 1136

LA 4329

UVA UVALive

Code:

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int MAXN = 100000+9;int a[MAXN];int n;int c[MAXN],d[MAXN];int tree[MAXN];int lowbit(int x){    return x&-x;}void addnum(int pos,int v){    int i;    for(i=pos;i<=100000;i+=lowbit(i))        tree[i]+=v;}int getsum(int pos){    int i;    int re=0;    for(i=pos;i>=1;i-=lowbit(i))        re+=tree[i];    return re;}void solve1(){    int i;    for(i=1;i<=100000;i++)        tree[i]=0;    for(i=1;i<=n;i++){        addnum(a[i],1);        c[i]=getsum(a[i]-1);    }    for(i=1;i<=100000;i++)        tree[i]=0;    for(i=n;i>=1;i--){        addnum(a[i],1);        d[i]=getsum(a[i]-1);    }}void solve2(){    int i;    LL ans=0;    for(i=1;i<=n;i++){        ans+=(LL)c[i]*(n-i-d[i]);        ans+=(LL)(i-c[i]-1)*d[i];    }    printf("%lld\n",ans);}int main(){    int kase;    scanf("%d",&kase);    while(kase--){        scanf("%d",&n);        int i;        for(i=1;i<=n;i++)            scanf("%d",&a[i]);        solve1();        solve2();    }    return 0;}

• 私有
• 公开
• 删除