第一次写树状数组，感觉那个lowbit位运算用的相当厉害。
因为-x相当于把x的二进制位取反然后整体再加上1，所以最右边的一个1以及末尾的0，取反加一以后不变。
比如1000取反是0111加一得到1000，这样与运算以后不变
最右边的1左边部分取反，加一不会影响左半部分，所以与运算以后全部为0
对于这道题来说貌似不是很容易能联想到树状数组
注意题中说了每个人的技能值互不相同。
从左往右扫描每个a[i]，另x[a[i]] = 1，然后统计x[1]...x[a[i]-1]的和就是第i个人左边技能值比他小的人数c[i]，所以第i个人左边技能值比他大的人数就是i-1-c[i]
同样地，从右往左扫描a[i]，也另x[a[i]] = 1，统计x[1]...x[a[i]-1]的和就是这个人右边技能值比他小的人数d[i]，所以他右边技能值比他大的人数就是n-i-d[i]
在根据计数原理，求一下总的方案数就是sum{ c[i] * n-i-d[i] + d[i] * i-1-c[i] }
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std; inline int lowbit(int x) { return x & (-x); } struct Fenwicktree
{
int n;
vector<int> C; void resize(int n) { this->n = n; C.resize(n); }
void clear() { fill(C.begin(), C.end(), ); } int sum(int x)
{
int ret = ;
while(x)
{
ret += C[x];
x -= lowbit(x);
}
return ret;
} void add(int x, int d)
{
while(x <= n)
{
C[x] += d;
x += lowbit(x);
}
}
}f; const int maxn = + ;
int a[maxn], c[maxn], d[maxn]; int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
while(T--)
{
int n, maxa = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) { scanf("%d", &a[i]); maxa = max(maxa, a[i]); }
f.resize(maxa); f.clear();
for(int i = ; i <= n; i++)
{
f.add(a[i], );
c[i] = f.sum(a[i] - );
}
f.clear();
for(int i = n; i > ; i--)
{
f.add(a[i], );
d[i] = f.sum(a[i] - );
}
long long ans = ;
for(int i = ; i <= n; i++) ans += (long long)c[i]*(n-i-d[i]) + (long long)d[i]*(i--c[i]);
printf("%lld\n", ans);
} return ;
}
代码君