H - Distinct Integers
Editorial
/
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
長さ 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} が全て異なる。
制約
- 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 をみたす i が少なくとも 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 行ずつ出力せよ。
入力例 1
5 5 0 1 2 1 4 1 0 4 0 3 3 1 0 5 0 2 4 1 2 5
出力例 1
8 15 5
例としてクエリ 4 を考えます。 このクエリが与えられた時、A=(0,1,4,3,4) です。 また、条件をみたす l,r の組は、(l,r)=(2,3),(2,4),(3,4),(3,5),(4,5) の 5 個です。
入力例 2
30 30 14 24 18 7 20 10 0 27 27 29 27 20 23 29 27 0 11 10 0 12 19 7 21 12 11 7 27 11 21 0 1 6 21 1 27 29 0 23 21 1 1 5 0 3 24 1 3 6 1 9 16 1 16 26 1 0 11 0 29 27 0 25 29 0 4 24 1 10 23 1 18 24 0 22 14 0 13 10 1 2 29 0 7 12 0 27 14 1 18 20 0 23 7 0 15 20 1 1 24 0 24 7 0 24 20 1 7 16 0 15 27 0 23 10 1 11 13 1 4 8
出力例 2
53 3 10 6 23 34 31 57 16 116 3 94 28 3 10