P15094 [UOI 2025 II Stage] Three Queries

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.

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.