题目链接：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; }