树状数组

uvalive4329

#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;
const int maxn=20000;
int C[5*maxn+5],n;
inline int lowbit(int x)
{
    return x&-x;
}
int sum(int x)
{
    int ret=0;
    while(x>0){
        ret+=C[x];x-=lowbit(x);
    }
    return ret;
}
void add(int x,int d)
{
    while(x<=100001){
        C[x]+=d;x+=lowbit(x);

    }
}
int a[maxn+5],c[maxn+5],d[maxn+5];
int32_t main()
{
    IO;
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        memset(C,0,sizeof(C));
        for(int i=1;i<=n;i++){
            c[i]=sum(a[i]-1);
            add(a[i],1);
        }
        for(int i=1;i<=n;i++){
            d[i]=sum(a[i]-1)-c[i];
        }
        int ans=0;
        for(int i=2;i<=n-1;i++)
            ans+=c[i]*(n-i-d[i])+d[i]*(i-1-c[i]);
        cout<<ans<<endl;
    }
}