1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <iostream>
#include <cstring>
using namespace std;
const int maxn=100010;
int tree[maxn+10],l[maxn+10],r[maxn+10];
int lowbit(int x){
return x&(-x);
}
int sum(int x){
int res=0;
while(x>0){
res+=tree[x];
x-=lowbit(x);
}
return res;
}
void add(int x,int d){
while(x<=maxn){
tree[x]+=d;
x+=lowbit(x);
}
}
int main(){
int T;
long long ans;
cin>>T;
while(T--){
ans=0;
int n;
cin>>n;
int *a=new int[n+10];
memset(tree,0,sizeof(tree));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
l[i]=sum(a[i]);
add(a[i],1);
}
memset(tree,0,sizeof(tree));
for(int i=n;i>=1;i--){
r[i]=sum(a[i]);
add(a[i],1);
}
for(int i=1;i<=n;i++){
ans+=l[i]*(n-i-r[i])+r[i]*(i-l[i]-1);
}
cout << ans << endl;
}
return 0;
}
|