Скользящее окно фиксированной длины с подсчётом различных элементов за O(n)

Держим частотную таблицу элементов текущего окна и счётчик distinct. При сдвиге окна вправо на 1: добавляем новый правый элемент и убираем ушедший левый, обновляя distinct инкрементально.

Правило обновления:

• При добавлении x: если его частота была 0 → distinct++, потом cnt[x]++.
• При удалении x: cnt[x]--, и если стала 0 → distinct--.

vector<int> distinctInWindows(const vector<int>& a, int k) {
    unordered_map<int,int> cnt;
    int distinct = 0;
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        if (cnt[a[i]]++ == 0) distinct++;            // вошёл правый
        if (i >= k) {                                // вышел левый
            if (--cnt[a[i - k]] == 0) distinct--;
        }
        if (i >= k - 1) res.push_back(distinct);     // окно сформировано
    }
    return res;
}

Каждый элемент один раз входит в окно и один раз выходит → суммарно O(n) операций (амортизированно O(1) на сдвиг). Если значения большие/разреженные — unordered_map, иначе обычный массив частот по сжатым значениям (быстрее, без хеш-константы). Память O(min(n, k) + alphabet).

Ключ — обновлять distinct в момент перехода частоты через ноль: 0→1 при добавлении даёт +1, 1→0 при удалении даёт −1. Это и есть весь инвариант скользящего окна для distinct.