UVALive - 4329 Ping pong （树状数组）

题意：一条街上住着n个乒乓球爱好者要组织比赛，每场比赛需要3个人，两个选手一个裁判，他们有一个奇怪的规定，即裁判必须住在两个选手之间，而且能力值也在两个选手之间，问一共能有几场比赛

思路：考虑第i个人当裁判的情形，假设a1到ai-1中有ci个比ai小，那么就有(i-1)-ci个比ai大

同理可以得到在ai+1到an的情况，那么就一共有:ci*(n-i-di)+di*(i-ci-1)种情况

然后按照树状数组的概念更新

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 100005;

int c[MAXN],x[MAXN],y[MAXN],a[MAXN],n;

void update(int x){
    while (x < MAXN)
        c[x]++,x += x&-x;
}

int sum(int x){
    int ans = 0;
    while (x > 0)
        ans += c[x],x -= x&-x;
    return ans;
}

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));
        //x[i]表示前i-1个比a[i]小的个数
        for (int i = 1; i <= n; i++){
            x[i] = sum(a[i]);
            update(a[i]);
        }
        memset(c,0,sizeof(c));
        for (int i = n; i >= 1; i--){
            y[i] = sum(a[i]);
            update(a[i]);
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++)
            ans += (long long)(x[i]*(n-i-y[i])) + (long long)((i-1-x[i])*y[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

UVALive - 4329 Ping pong （树状数组）

原文：http://blog.csdn.net/u011345136/article/details/19432759