Distinct Values - Add/Remove

Maintain a frequency array $cnt[v]$ = count of value $v$ in current range, and $distinctCount$ = number of values with $cnt > 0$.

Add operation:

function add(value)
    if cnt[value] = 0 then
        distinctCount := distinctCount + 1
    cnt[value] := cnt[value] + 1

Remove operation:

function remove(value)
    cnt[value] := cnt[value] - 1
    if cnt[value] = 0 then
        distinctCount := distinctCount - 1

Both are $O(1)$. Total time: $O((n + q)\sqrt{n})$.