Problem - Distinct Values

Given an array of $n$ integers and $q$ queries, each query asks: how many distinct values are in range $[l, r]$? Constraints: $n, q \leq 2 \cdot 10^5$, values up to $10^9$.

This problem is perfect for MO's algorithm.

Segment trees can't easily count distinct values, but extending a range by one element is simple: check if you've seen this value before in the current range. Before reading the solution, think about how you'd implement the $add$ and $remove$ functions.