UVALive 4329 Ping pong （BIT）

枚举中间的人，只要知道在这个人前面的技能值比他小的人数和后面技能值比他小的人数就能计算方案数了，技能值大的可有小的推出。

因此可以利用树状数组，从左到右往树上插点，每个点询问sum(a[i]-1)就是前面的技能值比它小的人数，然后再从右边往左重复一遍就可以算出答案。

#include<bits/stdc++.h>
using namespace std;

const int maxa = 1e5+2;
#define lowbit(x) (x&-x)
int C[maxa];
int sum(int x)
{
    int ret = 0;
    while(x>0){
        ret += C[x]; x -= lowbit(x);
    }
    return ret;
}

int r;
//x >0
void add(int x,int d)
{
    while(x<=r){
        C[x] += d; x += lowbit(x);
    }
}

const int maxn = 2e4+5;
int a[maxn],p[maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    int T; cin>>T;
    while(T--){
        int n; scanf("%d",&n);
        r = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d",a+i); r = max(r,a[i]);
        }
        fill(C+1,C+1+r,0);
        for(int i = 0; i < n; i++){
            p[i] = sum(a[i]-1);
            add(a[i],1);
        }
        fill(C+1,C+1+r,0);
        long long ans = 0;
        for(int i = n-1; i >= 0; i--){
            int q = sum(a[i]-1);
            ans += (n-i-1-q)*p[i] + q*(i-p[i]);
            add(a[i],1);
        }
        printf("%lld
",ans);
    }
    return 0;
}

UVALive 4329 Ping pong （BIT）

相关推荐