10816번: 숫자 카드 2

https://www.acmicpc.net/problem/10816


$O(n+m)$

#include<cstdio>
#define s (int)1e7
int n, a[2 * s + 1], x;
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), a[x + s]++;
    for (scanf("%d", &n); n--;) scanf("%d", &x), printf("%d ", a[x + s]);
    return 0;
}

$O((n+m)\lg n)$

#include<cstdio>
#include<map>
using namespace std;
map<int, int> mp;
int n, x;
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), mp[x]++;
    for (scanf("%d", &n); n--;) scanf("%d", &x), printf("%d ", mp[x]);
    return 0;
}

$O((n+m)\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[500000], x;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    for (scanf("%d", &m); m--;) {
        scanf("%d", &x);
        printf("%d ", upper_bound(a, a + n, x) - lower_bound(a, a + n, x));
    }
    return 0;
}