← 返回题目列表

AtCoder · jsc2019_final_h

H. 不同的整数

中文机器翻译题面 查看原题

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