LA4329,poj3928树状数组原理和应用

题意：一条街上有n个人，每个人都有一个不同的值 a ，进行要求选3个人，1个裁判，2个选手，满足：裁判必须住在选手中间，裁判的值也要在选手中间。求能有多少种比赛。

思路：枚举第 i 个人当裁判，设 a0 到 ai-1 中，有 bi 个数比 ai 小，ai+1 到 an-1中有 di 个数比 ai 大，那么比赛种数为 b[i]*(n-i-1-d[i])+(i-b[i])*d[i].

要求 bi 和 di ，可以采用树状数组。ai 的最大值为100000，那么BIT的范围是1-100000，A[100000]的每个数 A[i] 代表一个人，一开始BIT中的每个位置上的数都是0，表示这个位置上没有人，C[ ] 表示BIT中的辅助数组，初始化为0。每当插入一个 ai ，相当于把值为 ai 的人放在BIT中的相应位置上，即对应位置上的值要加1，从初始的0变为1，此时需要修改相应的C[ ] 中的值。

由于我要求的是比 ai 小的数的个数，那么这些比 ai 小的数在BIT中的位置必然是在 ai 之前，也就是这些位置上的值为1，那么 A[ai] 的前缀和就等于这些数的个数。

当要求 ai+1 到 an-1 中比 ai 小的数时，把数组 a[] 反过来插入BIT中即可。

一个树状数组原理的讲解：http://kmplayer.iteye.com/blog/562119

#include<cstdio>
#include<cstring>
const int maxn=20000+10;
const int maxm=100000+10;
int C[maxm];//ai的最大范围
int n,b[maxn],d[maxn];
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<=maxm)
    {
        C[x]+=d;
        x+=lowbit(x);
    }
}
int main()
{
    int t,a[maxn];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        memset(C,0,sizeof(C));
        for(int i=0;i<n;i++)
        {
            add(a[i],1);
            b[i]=sum(a[i])-1;//减一是因为不能包括ai本身
        }
        memset(C,0,sizeof(C));
        for(int i=n-1;i>=0;i--)
        {
            add(a[i],1);
            d[i]=sum(a[i])-1;
        }
        long long ans=0;
        for(int i=1;i<n-1;i++)
            ans+=b[i]*(n-i-1-d[i])+(i-b[i])*d[i];
        printf("%lld
",ans);
    }
    return 0;
}

View Code

LA4329,poj3928树状数组原理和应用

相关推荐