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;
}
原文：http://www.cnblogs.com/yspworld/p/4243569.html