← 返回题目列表

AtCoder · pakencamp_2024_day2_f

F. 法国餐厅

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

配点 : {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. (1 点) K = 1
  2. (9 点) N, Q \leq 2000
  3. (30 点) K = 2
  4. (15 点) T_i = 1, 3 (1 \leq i \leq Q)
  5. (15 点) T_i = 2, 3 (1 \leq i \leq Q)
  6. (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 变为。