uva 1428 - Ping pong(樹狀數組)

uva 1428 - Ping pong(樹狀數組)

題目鏈接：uva 1428 - Ping pong

題目大意：一條大街上住著n個乒乓球愛好者，經常組織比賽。每個人都有一個不同的能力值，每場比賽需要3個人，裁判要住在兩個選手之間，並且能力值也要在選手之間，問說最多能舉行多少場比賽。

解題思路：預處理出bi和ci分別表示說在1~i中能力值比第i個人小的人和i+1~n中能力值比第i個人小的。處理過程用樹狀數組維護即可。

#include 
#include 
#include 

using namespace std;
#define lowbit(x) ((x)&(-x))
const int maxn = 1e5;
typedef long long ll;

int n, s[maxn+5];
int N, a[maxn+5];
ll b[maxn+5];

void add (int x, int v) {
    while (x <= n) {
        s[x] += v;
        x += lowbit(x);
    }
}

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

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &N);

        n = 0;
        memset(s, 0, sizeof(s));
        for (int i = 1; i <= N; i++) {
            scanf("%d", &a[i]);
            n = max(a[i], n);
        }

        for (int i = 1; i <= N; i++) {
            b[i] = sum(a[i]-1);
            //printf("%lld ", b[i]);
            add(a[i], 1);
        }
        //printf("\n");

        ll ans = 0;
        memset(s, 0, sizeof(s));
        for (int i = N; i > 0; i--) {
            ll d = sum(a[i]-1);
            add(a[i], 1);
            ans += (b[i] * (N - i - d)) + d * (i - 1 - b[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}