配点 : {100} 点
問題文
法国餐厅“Pakenche”的厨师帕肯先生正在准备晚餐时间。 准备好 N 个盘子,左右排成一排。每道菜都是 1 以上 K 用下面的整数表示美味 它的值为,当前从左侧开始。 i 菜的美味在于 D_i 。在 Pakenshe,每种口味都不同。 1, 2, \ldots, K 此订单的菜肴 1 一份一份的套餐变得非常受欢迎。
Phakeng 先生创造了这些物品,以确保他的客人尽可能满意。 对于 N 菜肴,以下内容 执行了 Q 操作。 i 操作类型是 1 以上 3 的整数 T_i 及其内容如下。
-
T_i = 1 ,重新煮菜, 从第 L_i 起 R_i 所有的菜都很美味。 改为 V_i 菜。
-
T_i = 2 ,在菜肴中添加配料, 第 L_i 起 R_i 美味 K 以前不及的菜肴美味 1 增加。不过在浇头之前,味道 K 是一道非常精致的菜,所以很好吃。 更改为 1 。 对于
-
T_i = 3 ,我们进行了以下思想实验:“在晚餐时间...... 10^{100} 假设有一位顾客来了。 从左边的菜肴开始,按顺序向一位顾客提供最多 L_i 起 R_i 的菜肴。此时,每种味道都是 1,2, \ldots, K 此订单的菜肴 1 每次可以服务多少位顾客? ”
请注意,这个思想实验不会改变食物的味道或使其消失。
作为Paken先生的学生,你需要找到Paken先生每个思想实验的正确答案。
制約
- 1 \leq N, Q \leq 150000
- 1 \leq K \leq 5
- 1 \leq D_i \leq K (1 \leq i \leq N)
- T_i 是 给出了 1, 2, 3 任何一个
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
- T_i = 1 然后,1 \leq V_i \leq K (1 \leq i \leq Q)
- 所有输入均为整数
小課題
- (1 点) K = 1
- (9 点) N, Q \leq 2000
- (30 点) K = 2
- (15 点) T_i = 1, 3 (1 \leq i \leq Q)
- (15 点) T_i = 2, 3 (1 \leq i \leq Q)
- (30 点)无附加约束
入力
输入是按以下格式从标准输入给出的。
N K
D_1 D_2 \ldots D_N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各 \mathrm{query}_i 包含多个以空格分隔的整数。 1 眼睛 T_i 。 \mathrm{query}_i 采用以下格式之一:
1 L_i R_i V_i
2 L_i R_i
3 L_i R_i
出力
思想实验的数量 作为 q , 输出 q 行。 打印第 i 行中, i 个思想实验的答案。
入力例 1
10 5 1 2 3 4 5 1 2 3 4 5 10 3 1 10 3 1 7 1 5 7 2 2 5 7 2 5 7 2 5 7 3 1 10 1 6 7 2 1 6 6 1 3 1 10
出力例 1
2 1 1 2
帕肯先生 10 准备不同的菜肴并按顺序品尝。 (1, 2, 3, 4, 5, 1, 2, 3, 4, 5) 。从现在起,帕肯先生 执行 10 操作:
-
1 在第二个动作中, 对第 1 起 10 道菜进行思想实验。 1 起 5 第道菜 1 提供给第 th 客户,6 起 10 第道菜 2 通过将其提供给客户,2 可以为多名客人提供套餐。3 由于无法向多个客户提供服务,因此答案是 2 变为。
-
2 在第二个动作中, 对第1 起 7 道菜进行思想实验。1 起 5 第道菜 1 通过为客户提供1 可以为多名客人提供套餐。2 由于无法向多个客户提供服务,因此答案是 1 变为。
-
3 对于第二个动作,我重新制作了它并 5 起 7 第二道菜的美味 换成 2 菜。美味有序 (1, 2, 3, 4, 2, 2, 2, 3, 4, 5) 。 满足
-
4 在第二个动作中,添加配料。 5 起 7 菜的美味 1 增加。美味有序 (1, 2, 3, 4, 3, 3, 3, 3, 4, 5) 。 满足
-
5 在第二个动作中,添加配料。 5 起 7 菜的美味 1 增加。美味有序 (1, 2, 3, 4, 4, 4, 4, 3, 4, 5) 。 满足
-
6 在第二个动作中,添加配料。 5 起 7 菜的美味 1 增加。美味有序 (1, 2, 3, 4, 5, 5, 5, 3, 4, 5) 。 满足
-
7 在第二个动作中, 对第1 起 10 道菜进行思想实验。1 起 5 第道菜 1 通过为客户提供1 可以为多名客人提供套餐。2 由于无法向多个客户提供服务,因此答案是 1 变为。
-
8 对于第二个动作,我重新制作了它并 6 起 7 第二道菜的美味 换成 2 菜。美味有序 (1, 2, 3, 4, 5, 2, 2, 3, 4, 5) 。 满足
-
9 对于第二个动作,我重新制作了它并 6 起 6 第二道菜的美味 换成 1 菜。美味有序 (1, 2, 3, 4, 5, 1, 2, 3, 4, 5) 。 满足
-
10 在第二个动作中, 对第 1 起 10 道菜进行思想实验。 1 起 5 第道菜 1 提供给第 th 客户,6 起 10 第道菜 2 通过将其提供给客户,2 可以为多名客人提供套餐。3 由于无法向多个客户提供服务,因此答案是 2 变为。