P1903 [CTT] Count Colors / Maintain Queue / [Template] Mo's Algorithm with Modifications

Momo bought a set of $N$ colored pens (some colors may be the same) and lined them up in a row. You need to answer Momo's requests. Momo will issue the following operations: 1. $Q\ L\ R$: Query how many distinct colors appear among the pens from the $L$-th to the $R$-th (inclusive). 2. $R\ P\ C$: Replace the $P$-th pen's color with $C$. To satisfy Momo's requests, can you process these operations?

The first line contains two integers $N$, $M$, representing the initial number of pens and the number of operations, respectively. The second line contains $N$ integers, where the $i$-th integer is the color of the $i$-th pen in the initial row. From line $3$ to line $2+M$, each line describes one operation; see the description above for the format.

For each query operation, output a single integer on its own line: the number of distinct colors among the pens from the $L$-th to the $R$-th.

For 30% of the testdata, $n,m \leq 10000$. For 60% of the testdata, $n,m \leq 50000$. For all testdata, $n,m \leq 133333$. All integers appearing in the input are between $1$ and $10^6$ inclusive. This problem may be slightly tight on constant factors. Source: bzoj2120. The testdata for this problem are created by Luogu, using [CYaRon](https://github.com/luogu-dev/cyaron), and took 5 minutes to generate. Translated by ChatGPT 5