Частоты и различные — разбор задачи

1. Идея

Нужно обрабатывать поток операций над кодами:

• добавить код x,
• узнать, сколько раз встречался код x,
• узнать, сколько разных кодов уже было добавлено.

Так как коды могут быть большими (до 10^9), хранить массив по значениям нельзя.
Подходит словарь: для каждого кода будем хранить число его добавлений.

Дополнительно удобно отдельно хранить количество различных кодов. Тогда запрос типа 3 можно отвечать сразу, за O(1).

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

Наблюдение 1

Для запроса 2 x нужно знать только текущее количество добавлений x.
Это стандартная задача на подсчёт частот: используем map или unordered_map в C++, dict в Python.

Наблюдение 2

Запрос 3 спрашивает количество различных кодов, то есть сколько значений x хотя бы раз встречались среди операций добавления.

Если при операции 1 x код x встречается впервые, то число различных кодов увеличивается на 1.

Наблюдение 3

Удалений в задаче нет. Значит:

• если код уже появился, он навсегда остаётся среди различных;
• количество различных кодов никогда не уменьшается.

Это делает решение совсем простым.

3. Алгоритм

Будем хранить:

• cnt — словарь, где cnt[x] равно числу добавлений кода x;
• distinct — текущее количество различных кодов.

Дальше обрабатываем операции по одной:

Операция 1 x

• если x ещё не встречался, то:
  • увеличиваем distinct на 1;
• увеличиваем cnt[x] на 1.

Операция 2 x

• выводим cnt[x], если такой код есть;
• иначе выводим 0.

Операция 3

• выводим distinct.

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

Докажем, что алгоритм всегда выдаёт правильные ответы.

Для словаря cnt

После каждой операции типа 1 x мы увеличиваем значение cnt[x] на 1.
Других операций, меняющих количество добавлений, нет.
Значит, в любой момент cnt[x] действительно равно числу операций 1 x, выполненных ранее.

Следовательно, запрос 2 x отвечает правильно:

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

Для переменной distinct

Мы увеличиваем distinct только тогда, когда код x добавляется впервые, то есть до этого его частота была 0.

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

Значит, в любой момент distinct равно количеству кодов, которые уже встречались хотя бы один раз.
Именно это и требуется в запросе типа 3.

Итак, все ответы корректны.

5. Сложность

Пусть n — число операций.

По времени

Каждая операция обрабатывается в среднем за O(1) при использовании хеш-таблицы:

• добавление в словарь,
• поиск в словаре,
• вывод distinct.

Итоговая средняя сложность: O(n).

По памяти

В словаре хранятся только коды, которые хотя бы раз добавлялись.
Если таких кодов k, то память O(k), где k <= n.

6. Код на C++17

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

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

    unordered_map<long long, long long> cnt;
    long long distinct = 0;

    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;

        if (type == 1) {
            long long x;
            cin >> x;
            if (cnt[x] == 0) {
                distinct++;
            }
            cnt[x]++;
        } else if (type == 2) {
            long long x;
            cin >> x;
            if (cnt.find(x) == cnt.end()) {
                cout << 0 << "\n";
            } else {
                cout << cnt[x] << "\n";
            }
        } else if (type == 3) {
            cout << distinct << "\n";
        }
    }

    return 0;
}

7. Код на Python 3

n = int(input())

cnt = {}
distinct = 0

for _ in range(n):
    parts = input().split()
    t = int(parts[0])

    if t == 1:
        x = int(parts[1])
        if x not in cnt:
            cnt[x] = 1
            distinct += 1
        else:
            cnt[x] += 1
    elif t == 2:
        x = int(parts[1])
        print(cnt.get(x, 0))
    else:
        print(distinct)