開始用瓜神说的方法撸了一发线段树。早上没事闲的看了一下树状数组的方法，于是又写了一发树状数组

树状数组：

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <climits>

#include <string>

#include <iostream>

#include <map>

#include <cstdlib>

#include <list>

#include <set>

#include <queue>

#include <stack>

using namespace std;

#define INF 0xfffffff

const int maxn=100010;

typedef long long LL;

int c[maxn],lmin[maxn],lmax[maxn],rmin[maxn],rmax[maxn],a[maxn];

int lowbit(int x)

{

    return x&(-x);

}

void update(int i,int l)

{

    while(i<maxn)

    {

        c[i]+=l;

        i+=lowbit(i);

    }

}

int sum(int i)

{

    int ans=0;

    while(i>0)

    {

        ans+=c[i];

        i-=lowbit(i);

    }

    return ans;

}

int main()

{

    int t,n;

    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++)

        {

            update(a[i],1);

            lmin[i]=sum(a[i]-1);

            lmax[i]=i-1-lmin[i];

            //cout<<lmin[i]<<" "<<lmax[i]<<endl;

        }

        memset(c,0,sizeof(c));

        for(int i=n;i>=1;i--)

        {

            update(a[i],1);

            rmin[i]=sum(a[i]-1);

            rmax[i]=n-i-rmin[i];

            //cout<<rmin[i]<<" "<<rmax[i]<<endl;

        }

        LL ans=0;

        for(int i=1;i<=n;i++)

        {

            ans+=lmin[i]*rmax[i];

            ans+=lmax[i]*rmin[i];

        }

        cout<<ans<<endl;

    }

    return 0;

}

线段树：

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <climits>

#include <string>

#include <iostream>

#include <map>

#include <cstdlib>

#include <list>

#include <set>

#include <queue>

#include <stack>

using namespace std;

#define INF 0xfffffff

typedef long long LL;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define maxn 100000+10

int a[maxn];

int sum[maxn<<2],zmax[maxn],zmin[maxn],ymax[maxn],ymin[maxn];

void pushup(int rt)

{

    sum[rt]=sum[rt<<1]+sum[rt<<1|1];

}

void build(int l,int r,int rt)

{

    sum[rt]=0;

    if(l==r) return ;

    int m=(l+r)>>1;

    build(lson);

    build(rson);

}

int ask(int L,int R,int l,int r,int rt)

{

    if(L<=l&&R>=r) return sum[rt];

    int m=(l+r)>>1;

    int ans=0;

    if(L<=m) ans+=ask(L,R,lson);

    if(R>m) ans+=ask(L,R,rson);

    return ans;

}

void update(int pos,int add,int l,int r,int rt)

{

    if(l==r)

    {

        sum[rt]=1;

        return ;

    }

    int m=(l+r)>>1;

    if(pos<=m) update(pos,add,lson);

    else update(pos,add,rson);

    pushup(rt);

}

int main()

{

    int t;

    cin>>t;

    int n;

    while(t--)

    {

        cin>>n;

        int Max=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&a[i]);

            Max=max(Max,a[i]);

        }

        build(1,Max,1);

        for(int i=1;i<=n;i++)

        {

            zmin[i]=ask(1,a[i],1,Max,1);

            zmax[i]=ask(1,Max,1,Max,1)-zmin[i];

            update(a[i],1,1,Max,1);

        }

        build(1,Max,1);

        for(int i=n;i>=1;i--)

        {

            ymin[i]=ask(1,a[i],1,Max,1);

            ymax[i]=ask(1,Max,1,Max,1)-ymin[i];

            update(a[i],1,1,Max,1);

        }

        LL ans=0;

        for (int i = 1; i <= n; i++)

        {

			ans += zmin[i] * ymax[i];

			ans += zmax[i] * ymin[i];

		}

		cout<<ans<<endl;

    }

    return 0;

}