AT_jsc2019_final_h Distinct Integers

[problemUrl]: https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_h 長さ $ 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\

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 行ずつ出力せよ。

### 制約 - $ 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\