（LA 4329） Ping Pang --树状数组

本文主要是介绍（LA 4329） Ping Pang --树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：
http://acm.hust.edu.cn/vjudge/problem/13895

题意：
一条大街上住着n个乒乓球爱好者，他们经常组织比赛切磋。每个人都有一个技能值，每场比赛需要三个人，两名选手和一名裁判。他们有一个规定，裁判的技能值一定处于两个选手之间，并且也住在两个选手之间。问一共能组织多少场比赛？

分析：
考虑第i个人当裁判的情况。假设在a1,..,ai-1中有ci个人技能值比ai小，那么有i-ci-1个人比ai技能值大。同理假设ai+1,…,an中有di个比ai小，则有（n-i）-di个比ai大。那么i当裁判有ci*（n-i-di）+(i-ci-1)*di种比赛。
所以题目就转化成了求ci,di了。假设有一个这样的数组x[N],当有选手技能值为i时x[i]=1,否则x[i]=0;当我们计算ci时，我们用a1,..ai-1更新x数组，那么ci=x[1]+x[2]+..+x[ai-1]。初始时x[i]=0,计算ci时就是求x[]的前缀和。这就是树状数组可以快速解决的问题了。计算di时一样。

AC代码：

#include<cstdio>
#include<vector>
using namespace std;//inline int lowbit(int x) { return x&(x^(x-1)); }
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(), 0); }// ¼ÆËãA[1]+A[2]+...+A[x] (x<=n)int sum(int x) {int ret = 0;while(x > 0) {ret += C[x]; x -= lowbit(x);}return ret;}// A[x] += d (1<=x<=n)void add(int x, int d) {while(x <= n) {C[x] += d; x += lowbit(x);}}
};const int maxn = 20000 + 5;
int n, a[maxn], c[maxn], d[maxn];
FenwickTree f;int main() {int T;scanf("%d", &T);while(T--) {scanf("%d", &n);int maxa = 0;for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); maxa = max(maxa, a[i]); }f.resize(maxa);f.clear();for(int i = 1; i <= n; i++) {f.add(a[i], 1);c[i] = f.sum(a[i]-1);}f.clear();for(int i = n; i >= 1; i--) {f.add(a[i], 1);d[i] = f.sum(a[i]-1);}long long ans = 0;for(int i = 1; i <= n; i++)ans += (long long)c[i]*(n-i-d[i]) + (long long)(i-c[i]-1)*d[i];printf("%lld\n", ans);}return 0;
}