LA 4329 Ping pong （树状数组）

题意：从左到右给你n个不同的数值，让你找出三个数值满足中间的数值在两边的数值之间的个数。

析：题意还是比较好理解的，关键是怎么求数量，首先我们分解一下只有两种情况，一个是左边<中间<右边，另一种是左边>中间>右边（因为数值都不相同嘛）。

我们考虑第i个数值在中间的情况。假设a1到ai-1中有ci个比ai小的，那么就有（i-1）-ci个比ai大的（因为不包括第i个数）。同理，假设有ai+1到an中有di个比ai小，那么有（n-i）-di个比ai大，那么一共就有ci（n-i-di） + （i-ci-1)di种。问题就转化为求ci和di。

ci可以这样计算：从左到右扫描所有的ai，令x[j]表示目前为止已经考虑过的所有的ai中是否存在一个ai=j（x[j] = 1表示存在， x[j] = 0表示不存在），则ci就是前缀和x[1]+x[2]+...+x[ai-1]。初始时所有x[i]=0，在计算ci时，要先设x[ai]=1；然后求前缀和。说到这就很明显是一个数状数组的题了。利用数状数组求前缀和时间复杂度低。在O(nlogr)（r为ai的上限）时间内可计算出ci。同理可计算出di。总是时间复杂度是O(n)。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 100000 + 10;

int sum[maxn], n, a[maxn], x[maxn], y[maxn];

int lowbit(int x){

    return x & (-x);

}

int getsum(int i){

    int s = 0;

    while(i > 0){

        s += sum[i];

        i -= lowbit(i);

    }

    return s;

}

void add(int i){

    while(i < maxn){

        ++sum[i];

        i += lowbit(i);

    }

    return ;

}

int main(){

    int T;   cin >> T;

    while(T--){

        scanf("%d", &n);

        memset(sum, 0, sizeof(sum));

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

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

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

            x[i] = getsum(a[i]);

            add(a[i]);

        }

        memset(sum, 0, sizeof(sum));

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

            y[i] = getsum(a[i]);

            add(a[i]);

        }

        long long ans = 0;

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

            ans += (long long)x[i] * (n-i-y[i]) + (long long)y[i] * (i-1-x[i]);

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

    }

    return 0;

}

巴特西

LA 4329 Ping pong （树状数组）

最新文章

热门文章