LA4329 Ping pong 乒乓比赛（树状数组与组合原理）

小咪咪 2021-12-11 13:03 144阅读 0赞

## 题意：   一条大街上住着n个乒乓球爱好者，经常组织比赛切磋技术。每个人都有一个能力值a\[i\]。每场比赛需要三个人：两名选手，一名裁判。他们有个奇怪的约定，裁判必须住在两名选手之间，而裁判的能力值也必须在两名选手之间。问一共能组织多少种比赛。 ##

## 分析：《训练指南》P197，考虑第i个人，假设a1到ai-1中有ci个比ai小，那么就有(i-1)-ci个比ai大；同理，如果ai+1到an中有di个比ai小，那么就有(n-i)-di个比ai大。i当裁判就有ci \* (n-i-di) + (i-1-ci)\*di种比赛。问题就转化为了计算数组c和数组d。这样的话就很容易想到使用树状数组去计算前缀和。   代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    inline int lowbit(int x) { return x&-x; }
    
    struct FenwickTree {
      int n;
      vector<int> C;
    
      void resize(int n) { this->n = n; C.resize(n); }
      void clear() { fill(C.begin(), C.end(), 0); }
    
      int sum(int x) {
        int ret = 0;
        while(x > 0) {
          ret += C[x]; x -= lowbit(x);
        }
        return ret;
      }
    
      void add(int x, int d) {
        while(x <= n) {
          C[x] += d; x += lowbit(x);
        }
      }
    };
    
    const int maxn = 20000 + 5;
    int n, a[maxn], c[maxn], d[maxn];
    FenwickTree f;
    
    int main() {
      int T;
      scanf("%d", &T);
      while(T--) {
        scanf("%d", &n);
        int maxa = 0;
        for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); maxa = max(maxa, a[i]); }
        f.resize(maxa);
        f.clear();
        for(int i = 1; i <= n; i++) {
          f.add(a[i], 1);
          c[i] = f.sum(a[i]-1);
        }
        f.clear();
        for(int i = n; i >= 1; i--) {
          f.add(a[i], 1);
          d[i] = f.sum(a[i]-1);
        }
    
        long long ans = 0;
        for(int i = 1; i <= n; i++)
          ans += (long long)c[i]*(n-i-d[i]) + (long long)(i-c[i]-1)*d[i];
        printf("%lld\n", ans);
      }
      return 0;
    }