https://vjudge.net/problem/UVALive-4329
题意：
一条大街上住着n个兵乓球爱好者，经常组织比赛切磋技术。每个人都有一个不同的技能值ai。每场比赛需要3个人：两名选手，一名裁判。他们有一个奇怪的规定，即裁判必须住在两名选手的中间，并且技能值也在两名选手之间。问一共能组织多少种比赛。
思路：
想了好久才明白二叉索引树在这里的运用。
首先，就像训练指南上说的，考虑第i个人当裁判的情形。假设a1到ai-1中有ci个比ai小，那么就有（i-1）-ci个比ai大；同理，假设ai+1到an中有di个比ai小，那么就有（n-i）-di个比ai大。根据乘法原理和加法原理，i当裁判有ci（n-i-di）+（i-ci-1）di种比赛。这样，问题就转化为ci和di。
接下来就是二叉索引树的应用，我们从左往右扫描a[i]，计算c[]值。
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std; const int maxn = + ;
int n;
int a[maxn],c[maxn],s1[maxn],s2[maxn]; int lowbit(int x)
{
return x&-x;
} int sum(int x)
{
int ret = ;
while (x > )
{
ret += c[x];
x -= lowbit(x);
}
return ret;
} void add(int x, int d)
{
while (x <= maxn)
{
c[x] += d;
x += lowbit(x);
}
} int main()
{
ios::sync_with_stdio(false);
//freopen("D:\\txt.txt", "r", stdin);
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = ; i <= n; i++)
cin >> a[i];
memset(c, , sizeof(c));
for (int i = ; i <= n; i++)
{
add(a[i], );
s1[i] = sum(a[i] - );
}
memset(c, , sizeof(c));
for (int i = n; i >= ; i--)
{
add(a[i], );
s2[i] = sum(a[i] - );
}
long long ans = ;
for (int i = ; i <= n-; i++)
{
ans += s1[i] * (n - i - s2[i]) + (i - s1[i] - )*s2[i];
}
cout << ans << endl;
}
}