配点 : 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