Count distinct values in every window of size k

• Keep a count for each ID inside the current window.
• When the window slides, add the new ID and decrement the old one. Erase it when its count reaches 0, so that size() equals the number of distinct IDs.

Sliding window with a frequency map.

1. Put the first k IDs into unordered_map<int,int> cnt. The answer for the first window is cnt.size().
2. For each new index i (from k to n−1):

• ++cnt[a[i]] adds the entering ID.
• if (--cnt[a[i-k]] == 0) cnt.erase(a[i-k]); removes the leaving ID.
• Record cnt.size().

Each step does a constant number of hash operations, so the total is O(n) expected time and O(k) memory. Rebuilding a set for every window costs O(n·k), which is too slow when n = 10^5 and k = 5·10^4.

C++ notes

• cnt[x] inserts x with value 0 if it is missing. That is why the erase step is needed to keep size() honest.
• unordered_map has expected O(1) operations but O(n) in the worst case, for example with adversarial keys. std::map guarantees O(log n). In contests people sometimes reserve buckets (cnt.reserve(2 * k)) or use a custom hash.