HDU5147 树状数组

好久没用树状数组了

用树状数组去求顺序数, b[i]是小于等于第i个的顺序数的个数; c[i]是大于第i个的顺序数的个数; 然后乘法原理去算;

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;
const int maxn = 100005;

int C[maxn], b[maxn], c[maxn], a[maxn];
int n;

int lowbit(int x){
    return x & (-x);
}

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);
    }
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        for(int i=1;i<=n;i++){
            scanf("%d", &a[i]);
        }
        memset(C, 0, sizeof(C));
        for(int i=1;i<=n;i++){
            b[i] = sum(a[i]);
            // printf("%d ", b[i]);
            add(a[i], 1);
            // for(int i=1;i<=n;i++){
            //     printf("%s%d%s", i==1?"C[i]":"", C[i], i<n?" ":"\n");
            // }
        }
        memset(C, 0, sizeof(C));
        for(int i=n;i>=1;i--){
            c[i] = sum(n) - sum(a[i]) + c[i+1];
            add(a[i], 1);
        }
        ll ans = 0;
        for(int i=2;i<=n-2;i++){
            ll t1 = b[i];
            ll t2 = c[i+1];
            ans += t1 * t2;
        }
        printf("%lld\n", ans);
    }
    return 0;
}