好久没用树状数组了
用树状数组去求顺序数, b[i]是小于等于第i个的顺序数的个数; c[i]是大于第i个的顺序数的个数; 然后乘法原理去算;
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 100005;
int C[maxn], b[maxn], c[maxn], a[maxn];
int n;
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 <= n){
C[x] += d;
x += lowbit(x);
}
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
}
memset(C, 0, sizeof(C));
for(int i=1;i<=n;i++){
b[i] = sum(a[i]);
// printf("%d ", b[i]);
add(a[i], 1);
// for(int i=1;i<=n;i++){
// printf("%s%d%s", i==1?"C[i]":"", C[i], i<n?" ":"\n");
// }
}
memset(C, 0, sizeof(C));
for(int i=n;i>=1;i--){
c[i] = sum(n) - sum(a[i]) + c[i+1];
add(a[i], 1);
}
ll ans = 0;
for(int i=2;i<=n-2;i++){
ll t1 = b[i];
ll t2 = c[i+1];
ans += t1 * t2;
}
printf("%lld\n", ans);
}
return 0;
}