树状数组：解决比某个数小的数的出现次数

浏览数：20 / 时间：2015年06月08日

 1 //输入一串n个数字，然后进行m次询问
 2 //每次询问中询问一个在上述数字串出现过的一个数，问比这个数字小的数字有几个
 3 //出现的重复的数字当作一个数字处理
 4 //n<=1000000, m<=100000
 5 
 6 //  sample input:
 7 //  11
 8 //  4 5 5 8 9 1 0 0 100 99 45
 9 //  3
10 //  5
11 //  100
12 //  9
13 
14 //  output:
15 //  3
16 //  8
17 //  5

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;


int a[1000001];
int c[1000002];

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

int sum(int x)
{
    int cnt=0;
    while(x>0)
    {
        cnt+=c[x];
        x-=lowbit(x);
    }
    return cnt;
}

int main()
{
    int n, m, dd， flag=0;
    int i, j;
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    int mm=-1;
    for(i=0; i<n; i++)
    {
        scanf("%d", &dd);
        if(dd==0)
            falg=1;
        if(dd>mm) mm=dd;
        a[dd]=1; //
    }
    //
    for(i=0; i<=mm; i++)
    {
        c[i]=0;
        for(j=i-lowbit(i)+1; j<=i; j++ )
        {
            c[i]+=a[j];
        }
    }
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d", &dd);
        printf("%d\n", sum(dd)-1+flag );
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

树状数组：解决比某个数小的数的出现次数