UVALive 4329 Ping pong（树状数组）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=13895

题意：一条街上住有n个乒乓选手，每个人都有一个技能值，现在每场比赛需要3个人，两个选手，一个裁判；裁判须住在他们之间，且其技能值必须在两选手之间，求一共能组织多少种比赛。

注意到技能值的范围(1 ≤ ai ≤ 100000），所以我们可以树状数组（O(nlogn)）处理得到一个ll数组，ll[x]表示住在x左边的并且技能值小于x的技能值的人数。类似逆着处理一次，得到一个rr数组，rr[x]表示住在x右边的并且技能值小于x的技能值的人数。

最后的答案便是： 

ans += ll[i] * (n - i - rr[i]) + (i - 1 - ll[i]) * rr[i] （1<= x <= n）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
#define maxm 20010
using namespace std;

typedef long long LL;

int player[maxm], c[maxn], ll[maxn], rr[maxn], n;

int lowbit(int x);

void add(int x, int u);

int sum(int x);

int main(void)
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", player + i);
        }
        memset( c, 0, sizeof(c));
        for (int i = 1; i <= n; ++i)
        {
            ll[i] = sum( player[i] - 1);
            add( player[i], 1);
        }
        memset( c, 0, sizeof(c));
        for (int i = n; i >= 1; --i)
        {
            rr[i] = sum( player[i] - 1);
            add( player[i], 1);
        }
        LL ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            ans += ll[i] * (n - i - rr[i]) + (i - 1 - ll[i]) * rr[i];
        }
        printf("%lld
", ans);
    }
    return 0;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int x, int u)
{
    while (x <= maxn)
    {
        c[x] += u;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int result = 0;
    while (x > 0)
    {
        result += c[x];
        x -= lowbit(x);
    }
    return result;
}