题目描述

Given an array $a$ of length $n$ and $q$ queries. We also have a binary array $w$ of infinite length, initially all $w_i=1$.

There are three types of queries:

• $1 \ x$ --- toggle the value of $w_x$ (from $1$ to $0$, and vice versa).
• $2 \ l \ r$ --- count the number of unique numbers in the array $a$ in the range $[l, r]$ for which $w_{a_i}=1$ and $l \le i \le r$.
• $3 \ x \ t$ --- assign the value $t$ to $a_x$.

Provide an answer for each query of the second type.

输入格式

The first line contains two integers $n$ and $q$ $(1 \le n, q \le 3\cdot10^5)$~--- the length of the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$~--- the values of the elements of the array.

Each of the following $q$ lines starts with an integer $type$ $(1 \le type \le 3)$ --- the type number of each query:

• If $type = 1$, the query contains one integer $x$ $(1 \le x \le 10^9)$ --- toggle the value of $w_x$.
• If $type = 2$, the query contains two integers $l$ and $r$ $(1 \le l \le r \le n)$ --- count the number of unique numbers in the array $a$ in the range $[l, r]$ for which $w_{a_i}=1$ and $l \le i \le r$.
• If $type = 3$, the query contains two integers $x$ and $t$ $(1 \le x \le n, 1 \le t \le 10^9)$ --- replace the value of $a_x$ with $t$.

输出格式

For each query of the second type, output the number of unique numbers in the range on a separate line.

10 5
3 4 3 4 3 2 3 1 2 1
2 2 5
1 3
2 2 5
3 4 5
2 2 5

2
1
2

提示

In the example for the first query of the second type, the segment looks like $[4, 3, 4, 3]$, meaning there are numbers $3$, $4$, and $w_3$, $w_4$ are equal to $1$, so the answer is $2$. After the next query of type $1$, $w_3$ becomes $0$, so for the next query, the answer is $1$. After the next query, the array will look like $[3, 4, 3, 5, 3, 2, 3, 1, 2, 1]$. In the last query, the segment will look like $[4, 3, 5, 3]$, meaning there are numbers $3, 4, 5$, respectively the answer is $2$, because $w_3 = 0$.

Scoring

• ($8$ points): $n, q \le 10^3$;
• ($6$ points): only queries of type $2$; $n=q; l_i=1$; $r_i=i$;
• ($13$ points): only queries of type $2$;
• ($10$ points): only queries of type $1$ and $2$; all $a_i$ are pairwise distinct;
• ($14$ points): only queries of type $1$ and $2$; all $w_{a_i}$ can change only once;
• ($7$ points): only queries of type $1$ and $2$;
• ($14$ points): only queries of type $2$ and $3$;
• ($8$ points): at any moment, $a_i \le 100$;
• ($10$ points): $n, q \le 5\cdot10^4$;
• ($10$ points): without additional constraints.