思路：

先排序，NlogN复杂度。

对每个要查询的数，先查找这个数，然后搜索其左右，得到该数出现的个数，NlogN复杂度。

但该方法的最坏复杂度是MNlogN，如果测试数据不好，时间上无法AC。改进方法：排序后遍历统计每个数的出现个数，另设与原数组同样大小的数组来存储，这样查找到的数就能直接找到出现个数，复杂度MlogN。

代码：

#include <stdio.h>

#include <stdlib.h>

#define N 1000000

#define M 1000

int cmp ( const void *a , const void *b )

{

    return *(int *)a - *(int *)b;

}

int main(void)

{

    int n, m, i;

    int a[N], b[M];

    while (scanf("%d", &n) != EOF)

    {

        for(i=0; i<n; i++)

            scanf("%d", &a[i]);

        scanf("%d", &m);

        for(i=0; i<m; i++)

            scanf("%d", &b[i]);

        qsort(a, n, sizeof(int), cmp);

        int *p, *ptmp;

        int count;

        for(i=0; i<m; i++)

        {

            p = (int *)bsearch(&b[i], a, n, sizeof(a[0]), cmp);

            //printf("find index = %d, key = %d\n", p-a, p[0]);

            if (p == NULL)

                count = 0;

            else

                count = 1;

            ptmp = p;

            if (p != NULL)

            {

                p++;

                while (p - a <= n)

                {

                    if (*p == b[i])

                    {

                        p++;

                        count++;

                    }

                    else

                        break;

                }

            }

            //printf("%d\n", count);

            p = ptmp;

            if (p != NULL)

            {

                p--;

                while (p - a >= 0)

                {

                    if (*p == b[i])

                    {

                        p--;

                        count++;

                    }

                    else

                        break;

                }

            }

            printf("%d\n", count);

        }

    }

    return 0;

}

/**************************************************************

    Problem: 1349

    User: liangrx06

    Language: C

    Result: Accepted

    Time:950 ms

    Memory:8656 kb

****************************************************************/