千萬次的問

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;}