hdu2492 Ping pong

题意：一群乒乓爱好者居住在一条直线上，如果两个人想打比赛需要一个裁判，裁判的位置必须在两者之间，裁判的能力也必须不大于参赛者最大的，不小于参赛者最小的

白皮的题解：考虑第 i 个为裁判的情况如果左边比 a[i] 小的人数为 c[i],则有 i-c[i]-1 个人比 a[i] 大，同样右边比 a[i] 小的人数为 d[i] ，则比a[i]大的人为 n - i - d[i];

则方案为 d[i]*( i - c[i] - 1 ) + c[i] * (n - i - d[i])

用 x[ a[i] ] 表示比 a[i] 小的个数，这就涉及到了树状数组

代码……

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <map>

#include <queue>

#include <stack>

#include <set>

#include <string>

using namespace std;

typedef long long ll;

const double ESP = 10e-;

const int MOD = ;

typedef long long LL;

const int MAXN =  + ;

const int MAXA =  + ;

int bit[MAXA];

int c[MAXN];

int d[MAXN];

int arr[MAXN];

int sum(int i){

    int s = ;

    while(i > ){

        s += bit[i];

        i -= i&-i;

    }

    return s;

}

void add(int i,int x){

    while(i < MAXA){

        bit[i] += x;

        i += i&-i;

    }

}

int main(){

//    freopen("input.txt","r",stdin);

    int t;

    scanf("%d",&t);

    while(t--){

        int n;

        scanf("%d",&n);

        memset(bit,,sizeof(bit));

        memset(c,,sizeof(c));

        memset(d,,sizeof(d));

        for(int i = ;i <= n;i++){

            scanf("%d",&arr[i]);

            c[i] = sum(arr[i]);

            add(arr[i],);

        }

        memset(bit,,sizeof(bit));

        for(int i = n;i > ;i--){

            d[i] = sum(arr[i]-);

            add(arr[i],);

        }

        LL ans = ;

        for(int i = ;i <= n;i++){

            ans += c[i]*(n-i-d[i]) + d[i]*(i-c[i]-);

        }

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西

hdu2492 Ping pong

最新文章

热门文章