1. Идея

Нужно отвечать на запросы вида: сколько различных товаров встретилось не менее t раз.

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

Главная мысль такая:

• сначала посчитаем, сколько раз встречается каждый товар;
• потом узнаем, сколько товаров имеют частоту 1, сколько имеют частоту 2, ..., сколько имеют частоту n;
• после этого построим массив, где для каждого t будет сразу храниться число товаров с частотой не меньше t.

Тогда каждый запрос обрабатывается за O(1).

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

Наблюдение 1

Каждый товар характеризуется только своей частотой появления в массиве.

Например, если покупки такие:

5 5 -1 7 7

то частоты товаров:

• 5 встречается 2 раза
• -1 встречается 1 раз
• 7 встречается 2 раза

Значит:

• частота 1 есть у 1 товара
• частота 2 есть у 2 товаров

Наблюдение 2

Пусть cnt[f] — сколько различных товаров встретились ровно f раз.

Тогда ответ на запрос t — это количество товаров с частотой t, t+1, t+2, ..., n.

То есть ответ равен сумме:

cnt[t] + cnt[t+1] + ... + cnt[n]

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

Наблюдение 3

Если suf[t] — количество товаров, встречающихся не менее t раз, то:

• suf[n] = cnt[n]
• suf[n-1] = cnt[n-1] + cnt[n]
• ...
• suf[i] = cnt[i] + suf[i+1]

Тогда ответ на запрос t — просто suf[t].

3. Алгоритм

1. Считываем n.
2. Считываем массив покупок.
3. С помощью словаря считаем частоту каждого товара.
4. Создаём массив cnt длины n + 1, где cnt[f] — число товаров, встретившихся ровно f раз.
5. Проходим по всем частотам из словаря и увеличиваем cnt[f].
6. Строим массив суффиксных сумм suf:
   • идём от n до 1
   • suf[i] = suf[i + 1] + cnt[i]
7. Считываем q.
8. Для каждого запроса t выводим suf[t].

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

Докажем корректность алгоритма.

После подсчёта словарём для каждого товара известна его точная частота появления в списке покупок.

Далее массив cnt хранит количество товаров для каждой возможной частоты:

• cnt[1] — сколько товаров купили ровно 1 раз,
• cnt[2] — сколько товаров купили ровно 2 раза,
• ...
• cnt[n] — сколько товаров купили ровно n раз.

Теперь рассмотрим запрос с порогом t. По условию нужно посчитать, сколько различных товаров были куплены не менее t раз. Это означает, что нас интересуют все товары с частотой:

• ровно t,
• ровно t+1,
• ...
• ровно n.

Их количество равно сумме cnt[t] + cnt[t+1] + ... + cnt[n].

Именно эту сумму хранит suf[t], потому что массив suf построен как суффиксная сумма массива cnt.

Значит, для каждого запроса ответ suf[t] в точности совпадает с требуемым количеством товаров.

Следовательно, алгоритм работает правильно.

5. Сложность

Пусть n — число покупок, q — число запросов.

• Подсчёт частот: O(n)
• Построение массива cnt: O(k), где k — число различных товаров, а k <= n
• Построение массива suf: O(n)
• Ответы на запросы: O(q)

Итоговая сложность: O(n + q)

По памяти:

• словарь частот — O(k)
• массивы cnt и suf — O(n)

Итоговая память: 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]++;
    }

    vector<int> cnt(n + 1, 0);
    for (auto &p : freq) {
        cnt[p.second]++;
    }

    vector<int> suf(n + 2, 0);
    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + cnt[i];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        cout << suf[t] << '\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

cnt = [0] * (n + 1)
for f in freq.values():
    cnt[f] += 1

suf = [0] * (n + 2)
for i in range(n, 0, -1):
    suf[i] = suf[i + 1] + cnt[i]

q = int(input())
for _ in range(q):
    t = int(input())
    print(suf[t])