首页 > 代码库 > [ACM] hdu 5147 Sequence II (树状数组,前缀和,后缀和)

[ACM] hdu 5147 Sequence II (树状数组,前缀和,后缀和)

Sequence II




Problem Description
Long long ago, there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n, and all numbers are different in this sequence.
Please calculate how many quad (a,b,c,d) satisfy:
1. 1a<b<c<dn
2. Aa<Ab
3. Ac<Ad
 

Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with a line contains an integer n.
The next line follows n integers A1,A2,,An.

[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <= Ai <= n
 

Output
For each case output one line contains a integer,the number of quad.
 

Sample Input
1 5 1 3 2 4 5
 

Sample Output
4
 

Source
BestCoder Round #23


解题思路:参考http://www.cnblogs.com/pdev/p/4176056.html

题意为给定1~n的一个排列 用A[ ]数组保存,问有多少下标(a,b,c,d)四 元组满足:

a<b<c<d 且 A[a] < A[b]   ,    A[c] < A[d].

题目中n的范围是50000,O(n^2) 复杂度超时.....

思路为: 枚举c的位置,那么每一次枚举中的方法数为 1到c-1中 (a,b)的个数 乘以  c到n中(c,d)的个数.累加起来即为答案。

1-c-1中(a,b)的个数相当于枚举b的位置,然后计算出b前面有多少数比A[b]小,该值要保存下来,下一次枚举c的时候,该值再加上c-1前面有多少比a[c-1]小的数即为当前情况下1-c-1中(a,b)的个数,也就是b=c-1的时候,因为枚举b之前的情况已经算过了。

举个例子:

当c枚举到第3时,b已经枚举完了1,2,并把当前(a,b)的方法数保存,等c枚举到4时,刚才保存的数加上b=3的情况,即为当前情况下(a,b)的方法数.


求当b=多少的方法数,也就是求b前面有多少个数比它小。

求当c=多少的方法数,也就是求c后面有多少个数比它大。

用树状数组来做。本题n范围50000,而且每个数都不相同很关键。所以我们就开辟n个位置,一开始每个位置都是0,其实每个位置不是0就是1,因为每个数只有一个。

比如数 1 3 2 4 5

一开始  c数组 0 0 0 0 0

先统计,再输入,因为计算a[i]前面有多少比它小的数,不包括它自己,而树状数组计算和的时候,要包括它自己。

i=1,   树状数组求和前缀和 pre[1]=0 , 此时0 0 0 0 0  , 输入1,变为  1 0 0 0 0

i=2,a[2]=3,要看 3前面有多少个数,也就是看c数组的3个位置前面有多少个1,1代表已经输入,发现1 0 0 0 0前三个数只有一个1,也就是pre[2]=1 (输入的第二个数之前只有1个比它小的),输入3以后,c数组变为  1 0 1 0 0

i=3, a[3]= 2, 要看2前面有多少个数,也就是看c数组前2个位置前面有多少个1,发现10100前两个数中只有一个1,也就是pre[3]=1.


再求后缀和时,只要和上面一样倒过来输入就可以了。

代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=50010;
int a[maxn];
int pre[maxn],suf[maxn];//前缀和 后缀和
//pre[i] 本题中表示输入顺序中第i个数之前有多少个比它小的数
//suf[i] 本题中表示输入顺序中第i个数之后有多少个比它大的数
//比如输入 1 4 2 3 ,那么pre[2]=1,因为4之前只有1比它小,suf[2]=0,因为4之后没有比它大的数
int n;

///树状数组部分
int c[maxn]; //第i个位置代表第i个数,c[i]=0代表该数未输入,c[i]=1代表该数已经输入

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

void update(int i,int x)//在第i个位置上增加x
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}

int sum(int i) //c[1-i]之间的和
{
    int s=0;
    while(i>0)
    {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
///树状数组结束

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            pre[i]=sum(a[i]);//统计a[i]之前有多少个比它小的数
            update(a[i],1);//在a[i]位置上加1,表示已经存在
        }
        memset(c,0,sizeof(c));
        for(int i=n;i>=1;i--)
        {
            suf[i]=(n-i)-sum(a[i]);//倒着输入,第i个数后面有n-i个数,再看看这n-i个数中是不是存在比a[i]小的(即sum(a[i]))
            //,减去它们,就是a[i]后面所有比它大的
            update(a[i],1);
        }
        long long ans=0,dp=0;
        for(int i=1;i<=n-1;i++)//枚举c的位置
        {
            ans+=dp*suf[i];//dp表示输入顺序中第i-1个数之前有多少个数比第i-1个数小,在本题中也就是比b小的个数,i是c
            dp+=pre[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}





[ACM] hdu 5147 Sequence II (树状数组,前缀和,后缀和)