#790(Div.4) H2
作者:
昊子
,
2022-05-11 21:09:29
,
所有人可见
,
阅读 211
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
#define endl '\n'
int tr[200005];
int a[200005];
int n;
int lowbit(int x){
return x & -x;
}
void add(int x, int k){
for(int i = x; i <= n; i += lowbit(i))tr[i] += k;
}
int ask(int x){
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))sum += tr[i];
return sum;
}
int get(int x){
return x * (x - 1) / 2;
}
void solve(){
cin >> n;
vector<int> v(n + 1, 0);
int ans = 0;
for(int i = 1; i <= n; ++ i){
tr[i] = 0;
cin >> a[i];
v[a[i]] ++;
}
for(int i = n; i >= 1; -- i){
ans += ask(a[i] - 1);
add(a[i], 1);
}
for(int i = 1; i <= n; ++ i)ans += get(v[i]);
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}