Problem Description

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?

Input Format

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.

Output 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.

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

4
4
3
4

Hint

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, and took 5 minutes to generate.

Translated by ChatGPT 5