P2184 Greed Island

Facing the frenzied assault of the ants, Xiao FF’s Tower defence has failed. Humans have been forced into a bay on Greed Island. Now, behind Xiao FF lies the boundless sea, and ahead are mutated super ants. Xiao FF still has a bright future and does not want to die here, so he sends his last batch of modified SCVs to lay mines to stop the ants’ advance.

Xiao FF’s last line of defense is a trench of length $n$. Xiao FF has infinitely many types of mines, and each time an SCV can lay mines of a single type on the interval $[L, R]$, with this type being different from any type used before. Since the situation is urgent, at some moments Xiao FF may ask how many different types of mines are currently in the interval $[L', R']$, and he wants you to answer as quickly as possible.

The first line contains two integers $n$ and $m$, where $n$ is the length of the defense line and $m$ is the total number of SCV laying operations and Xiao FF’s queries. Each of the next $m$ lines contains three integers $q, l, r$: - If $q = 1$, the SCV lays mines of a single, previously unused type on the interval $[l, r]$. - If $q = 2$, Xiao FF asks how many different types of mines are currently in the interval $[l, r]$.

For each of Xiao FF’s queries, output one answer (one per line), which is the current number of mine types in the specified interval.

### Constraints - For $30\%$ of the testdata, $0 \le n, m \le 1000$. - For $100\%$ of the testdata, $0 \le n, m \le 10^5$. Translated by ChatGPT 5