1. Идея

Нужно много раз отвечать на один и тот же тип вопроса: сколько раз число v встречается в массиве.

Если для каждого запроса заново проходить по всему массиву и считать совпадения, получится слишком медленно: q запросов по n элементов, то есть до n * q, а это слишком много.

Поэтому выгодно один раз заранее посчитать, сколько раз встречается каждое значение, а потом для каждого запроса просто брать уже готовый ответ.

Для этого идеально подходит словарь:

• ключ — значение a_i,
• значение — сколько раз оно встретилось.

2. Наблюдения

1. Запросы независимы друг от друга. Ответ на запрос с кодом v зависит только от того, сколько раз v встретился в исходной последовательности.

2. Значения могут быть большими и отрицательными. Значит, обычный массив частот использовать неудобно. Нужна структура, которая умеет хранить частоты по произвольным целым ключам. Для этого подходит:

   • unordered_map в C++,
   • dict в Python.

3. После построения таблицы частот каждый запрос обрабатывается очень быстро:

   • если значение есть в словаре, выводим его частоту;
   • если нет, выводим 0.

3. Алгоритм

1. Считать n.
2. Считать n чисел.
3. Создать словарь частот freq.
4. Для каждого числа x из последовательности увеличить freq[x] на 1.
5. Считать q.
6. Для каждого из q запросов:
   • считать v,
   • если v есть в словаре, вывести freq[v],
   • иначе вывести 0.

4. Почему это работает

После обработки всех n чисел в словаре freq для каждого значения x хранится ровно количество его появлений в последовательности.

Это верно, потому что:

• в начале частота каждого числа равна 0;
• каждый раз, когда встречается число x, мы увеличиваем freq[x] на 1;
• значит, после просмотра всей последовательности freq[x] равно числу элементов, равных x.

Теперь рассмотрим запрос со значением v:

• если v был в последовательности, в freq[v] уже записано точное число его вхождений;
• если v не встречался, такого ключа нет в словаре, и ответ должен быть 0.

Следовательно, алгоритм выводит правильный ответ для каждого запроса.

5. Сложность

Построение словаря частот:

• O(n) в среднем.

Обработка всех запросов:

• O(q) в среднем.

Итоговая сложность:

• O(n + q) в среднем.

Память:

• O(k), где k — количество различных значений в последовательности.
• В худшем случае O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;

    unordered_map<long long, int> freq;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        freq[x]++;
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        long long v;
        cin >> v;
        if (freq.find(v) != freq.end()) {
            cout << freq[v] << '\n';
        } else {
            cout << 0 << '\n';
        }
    }

    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

freq = {}
for x in a:
    if x in freq:
        freq[x] += 1
    else:
        freq[x] = 1

q = int(input())
for _ in range(q):
    v = int(input())
    print(freq.get(v, 0))