AT_jsc2019_final_h Distinct Integers

有一个长度为 $N$ 的数列 $A_0,A_1,\cdots,A_{N-1}$。请你回答 $Q$ 个查询。具体来说，对于第 $i$ 个查询（$0 \leq i \leq Q-1$），给定整数 $T_i,X_i,Y_i$，请按如下方式操作： - 当 $T_i=0$ 时：将 $A_{X_i}$ 替换为 $Y_i$。 - 当 $T_i=1$ 时：请回答满足以下条件的整数对 $(l,r)$ 的个数（$X_i \leq l < r \leq Y_i$）： - $A_l,A_{l+1},\cdots,A_{r-1}$ 都互不相同。

输入以如下格式从标准输入给出。 > $N$ $Q$ $A_0$ $A_1$ $\cdots$ $A_{N-1}$ $T_0$ $X_0$ $Y_0$ $T_1$ $X_1$ $Y_1$ $\vdots$ $T_{Q-1}$ $X_{Q-1}$ $Y_{Q-1}$

对于每个 $T_i=1$ 的查询，按照查询给出的顺序，每行输出一个答案。

## 限制条件 - $1 \leq N \leq 5 \times 10^5$ - $1 \leq Q \leq 5 \times 10^5$ - $0 \leq A_i \leq N-1$ - $0 \leq T_i \leq 1$ - $0 \leq X_i \leq N-1,\ 0 \leq Y_i \leq N-1$（$T_i=0$） - $0 \leq X_i < Y_i \leq N$（$T_i=1$） - 至少存在一个 $T_i=1$ 的查询。 - 输入的所有值均为整数。 ## 样例解释 1 以第 4 个查询为例。当该查询给出时，$A=(0,1,4,3,4)$。满足条件的 $(l,r)$ 共有 $5$ 组，分别为 $(l,r)=(2,3),(2,4),(3,4),(3,5),(4,5)$。 由 ChatGPT 4.1 翻译