算法竞赛入门经典 p197
题目大意：
一条大街上住着n个乒乓球爱好者。常常比赛切磋技术。每一个人都有一个不同的技能值a[i]。每场比赛须要3个人：两名选手，一名裁判。他们有个奇怪的约定，裁判必须住在两名选手之间，而裁判的能力值也必须在两名选手之间。问一共能组织多少种比赛。
分析：
如果a[1]到a[i-1]中小于a[i]的数有p[i]。a[i+1]到a[n]中小于a[i]的数有s[i]个;
这样当i为裁判时可以组织的比赛数目为：p[i]*(n-i-s[i]) + (i-1-p[i])*s[i];
则总比赛次数为：
ans = 0; for i -> 1 to n (i表示选取第i个人作为裁判) ans += p[i]*(n-i-s[i]) + (i-1-p[i])*s[i];首先确定p[i]的值，令x[j]表示到眼下为止已经考虑过的全部a[i]中是否存在技能值为j的数；（x[j] = 0表示不存在，x[j] = 1表示存在）
memsest(x, 0, sizeof(x));(将x初始化为0);
for i -> 1 to cur (cur为考虑的当前位置,即选取的裁判位置）
x[a[i]] = 1;
则有 p[cur] = x[1]+x[2]+.....+x[a[cur]-1];
例：
如果 n = 4 a[1] = 2, a[2] = 3, a[3] = 5, a[4] = 1;
选取 cur= 3，a[cur] = 5; （第三个人做裁判）
p[3] = x[1]+x[2]+x[3]+x[4] = 0 + 1 + 1 + 0 = 2;（这里 x[1] = 0的原因是没有运行到第4个）
不断的记录求和，当然是没有问题的（时间开销非常大)
for i -> 1 to n;
x[a[i]] = 1;
p[i] = 0;
for j -> 1 to a[i]-1
p[i] += x[j]
改动单个元素并求前缀和是树状数组的标准使用方法，能够大幅度缩减时间（时间复杂度从O(nr)降到O(nlogr) );
for i-> 1 to n
add(a[i], 1); //(点改动)
p[i] = sum(a[i]-1); //(前缀和);到这里结果基本上能够求出来了，那s[i]呢？类似的。方向从i -> 1 to n 改为 i -> n todown 1就可以；代码例如以下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 20000+10;
const int maxm = 100000+10;
int c[maxm], a[maxn], p[maxn], s[maxn], n;
inline int lowbit(int x){
return x&-x;
}
void add(int x, int d){
while(x <= maxm){ // 一定注意这里是maxm, 原因能够思考一下;
c[x] += d; x += lowbit(x);
}
}
int sum(int x){
int ret = 0;
while(x > 0){
ret += c[x]; x -= lowbit(x);
}
return ret;
}
int main()
{
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; ++i){
add(a[i], 1);
p[i] = sum(a[i]-1);
}
memset(c, 0, sizeof(c));
for(int i = n; i > 0; --i){
add(a[i], 1);
s[i] = sum(a[i]-1);
}
long long ans = 0;
for(int i = 1; i <= n; ++i){
ans += p[i]*(n-i-s[i]) + (i-1-p[i])*s[i];
}
printf("%lld
", ans);
}
return 0;
}