hrbust 2015 千万次的问 前缀

千万次的问

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 225(77 users) Total Accepted: 80(58 users) Rating:  Special Judge: No

Description

现在给定一个数组array，数组的长度不会超过100000，而且数组中的每个元素都是一个正整数，每个元素的值不超过100000。对于一个给定的区间[a,b]，我们想要知道数组array中有多少个元素落在这个区间内。a，b属于(0, 100000]。

Input

本题只有一组输入数据，首先输入一个整数n代表数组的长度，接下来输入n个正整数。之后需要输入一个正整数m表示询问的次数，m不会超过10000000。随后的m行数输入两个正整数a和b，表示查询区间的两个端点，保证输入数据合法。

Output

对于每次查询输出一个整数表示数组array中有多少个数落在给定区间内并换行。

Sample Input

10 1 2 3 4 5 6 7 8 9 10 3 1 1 1 2 1 3

Sample Output

1 2 3

Source

杨和禹求职记

Author

杨和禹

#include <stdio.h>#include <string.h>int a[100002],b[100002];int main(){    int n,m,k;    memset(a,0,sizeof(a));    memset(b,0,sizeof(b));    scanf("%d",&n);    {        k=-1;        for(int i=0; i<n; i++)        {            scanf("%d",&m);            if(k<m)                k=m;            a[m]++;        }        for(int i=1; i<=k; i++)            b[i]+=b[i-1]+a[i];        int p,r,l;        scanf("%d",&p);        while(p--)        {            scanf("%d%d",&r,&l);            PRintf("%d/n",b[l]-b[r-1]);        }    }    return 0;}