1. Идея

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

Самая естественная структура для этого — словарь:

• ключ — идентификатор пользователя a_i;
• значение — сколько раз он уже встретился.

Когда читаем очередное число x:

1. увеличиваем cnt[x] на 1;
2. это новое значение и есть ответ для текущей позиции.

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

• Ответ для позиции i зависит только от элементов на префиксе, то есть от a_1, a_2, ..., a_i.
• Не нужно пересчитывать количество вхождений заново для каждого элемента: это было бы слишком медленно.
• Если хранить текущие количества в словаре, то каждое обращение можно обработать за константное время в среднем.

Пример:

Пусть массив такой: 7 3 7 7 3

Тогда идём по нему:

• 7 → встречался 1 раз → ответ 1
• 3 → встречался 1 раз → ответ 1
• 7 → встречался 2 раза → ответ 2
• 7 → встречался 3 раза → ответ 3
• 3 → встречался 2 раза → ответ 2

Итог: 1 1 2 3 2

3. Алгоритм

1. Считать n.
2. Создать словарь cnt для подсчёта количества появлений каждого идентификатора.
3. Создать массив ответов ans.
4. Для каждого из n чисел:
   • считать x;
   • увеличить cnt[x] на 1;
   • добавить cnt[x] в ans.
5. Вывести элементы массива ans через пробел.

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

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

Рассмотрим момент обработки некоторого элемента a_i = x.

До этого шага в словаре cnt[x] хранится количество появлений числа x среди уже обработанных элементов: a_1, a_2, ..., a_(i-1).

После выполнения cnt[x]++ значение cnt[x] становится равным количеству появлений x среди элементов: a_1, a_2, ..., a_i.

А по условию именно это число и нужно вывести для позиции i: сколько раз идентификатор a_i встретился от начала до текущего места включительно.

Значит, число, которое алгоритм записывает в ans[i], верно.

Так происходит для каждой позиции, следовательно, весь массив ответов строится правильно.

5. Сложность

• Время: O(n) в среднем, потому что для каждого элемента выполняется одно обращение к словарю.
• Память: 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> cnt;
    vector<int> ans(n);

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        cnt[x]++;
        ans[i] = cnt[x];
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

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

cnt = {}
ans = []

for x in a:
    cnt[x] = cnt.get(x, 0) + 1
    ans.append(cnt[x])

print(*ans)