LA 4329

UVA UVALive

Problem Link

其实我们只要利用树状数组就可以知道：某一位置前比它小的数的个数，以及其后比它大的个数，怎么着乘一下就有答案了。

可是我写这个并不是说这个题怎么了，而是关于树状数组，一定要非常注意树状数组的长度究竟是多少，就像本题中，长度不是 $n$ 而是 $max\{a[i]\}$,否则 WA×14 orz

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;
}