HDU 2492 - Ping pong

题目描述

Ping pong

解法：树状数组（C++）

我们先来翻译一下题目思路就来了，原题的描述有点绕：

每三个人进行一场比赛，裁判只能处在两个选手之后，且裁判的能力值要大于其中一个选手，而小于另外一个选手

好了，这就是题意，按照排列组合，是不是对每个裁判的位置左边取一个能力小于其的选手，右边取一个能力大于其的选手，就构成了一场比赛；反过来，左边取一个能力大于其的选手，右边取一个能力小于其的选手，就又构成了一场比赛

是不是超简单 (。???)ノ

这里，树状数组用两次，一次处理 $lleft[i]$，记录左边能力小于当前裁判位置的选手的个数；一次处理 $rright$，记录右边能力小于当前裁判位置的选手的个数

#include <iostream>
#include <string.h>using namespace std;const int N = 100005;
int T, n;
long long ans;
int a[20005], lleft[20005], c[N], rright;int lowbit(int x){
    return x&(-x);}void add(int x){
    for(int i=x;i<=N;i+=lowbit(i))c[i]++;
}int sum(int x){
    int s = 0;for(int i=x;i;i-=lowbit(i))s += c[i];return s;
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%d", &n);memset(c, 0, sizeof(c));for(int i=1;i<=n;i++){
    scanf("%d", &a[i]);add(a[i]);lleft[i] = sum(a[i]-1);}memset(c, 0, sizeof(c));ans = 0;for(int i=n;i;i--){
    add(a[i]);rright = sum(a[i]-1);ans += lleft[i]*(n-i-rright)+(i-1-lleft[i])*rright;}printf("%lld\n", ans);}return 0;
}