RMQ、树状数组板子

/*         ggg   ggg
        ggggggg ggggggg
      ggggggggggggggggggg
        ggggggggggggggg
          ggggggggggg
            ggggggg
              ggg
               g
*/
/*  gyt
       Live up to every day            */

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e5+5;
const ll maxm = 1e7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f;
const ll inf = 1e15 + 5;
const db eps = 1e-9;
int c[maxn], a[maxn], n, ca=1;
ll l[maxn], lm[maxn];
/*void RMQ_init() {
    for (int i = 1; i <= n; i++) {
        dmax[i][0] = dmin[i][0] = a[i];
    }
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 1; i+(1<<j)-1<=n; i++) {
            dmax[i][j] = max(dmax[i][j-1], dmax[i+(1<<(j-1))][j-1]);
            dmin[i][j] = min(dmin[i][j-1], dmin[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQma(int l, int r) {
    int k = 0;
    while((1<<(k+1))<=r-l+1)  k++;
    return max(dmax[l][k], dmax[r-(1<<k)+1][k]);
}
int RMQmi(int l, int r) {
    int k = 0;
    while((1<<(k+1))<=r-l+1)  k++;
    return min(dmin[l][k], dmin[r-(1<<k)+1][k]);
}*/
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<maxn) {
        c[x] += d;  x+=lowbit(x);
    }
}
void solve() {
    scanf("%d", &n);
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++) {
        scanf("%d", a+i);
    }
    ll ans=0;
    for (int i = 1; i <= n; i++) {
        l[i] = sum(a[i]);
        lm[i] = i-1-l[i];
        add(a[i], 1);
    }
    memset(c, 0, sizeof(c));
    for (int i = n; i > 0; i--) {
        ll tmp=sum(a[i]);
        ans += tmp*lm[i];
        tmp = n-i-tmp;
        ans += (tmp)*l[i];
        add(a[i], 1);
    }
    cout << ans << endl;
}
int main() {
    int t = 1;
    scanf("%d", &t);
    while(t--)
        solve();
    return 0;
}