AT_pakencamp_2024_day2_f French Restaurant

法国料理店“パケンシェ”的主厨パケン先生为了迎接晚餐时间，准备了 $N$ 道菜，并将它们依次排成一列。这些菜肴各自拥有一个介于 $1$ 到 $K$ 之间的整数数值，称为**美味度**，现在从左到右第 $i$ 道菜的美味度为 $D_i$。在“パケンシェ”，依次为客人提供美味度分别为 $1, 2, \ldots, K$ 的一道道菜的“套餐料理”非常受欢迎。 为了让到访的客人尽可能满意，パケン先生针对这 $N$ 道菜，进行了如下 $Q$ 次操作。第 $i$ 次操作的类型用 $T_i$（1 到 3 的整数）表示，含义如下： - 若 $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$ 的套餐？” 此思考实验不会改变菜肴的状态，也不会减少菜的数量。 作为パケン先生的弟子，你需要针对每次思考实验，给出正确答案。

输入按如下格式，从标准输入给出。 > $N$ $K$ $D_1$ $D_2$ $\ldots$ $D_N$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$ 每个 $\mathrm{query}_i$ 为若干个以空格分隔的整数，第一个一定是 $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. （$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$ 分）无其它额外限制 ### 样例解释 1 パケン先生准备了 $10$ 道菜，美味度依次为 $(1, 2, 3, 4, 5, 1, 2, 3, 4, 5)$。接下来他进行 $10$ 次操作： - 第 $1$ 次操作，对第 $1$ 到 $10$ 道菜做思考实验。前 $5$ 道菜提供给第 $1$ 位客人，后 $5$ 道菜提供给第 $2$ 位客人。这样最多能为 $2$ 位客人提供套餐，不能超过 $2$，答案为 $2$。 - 第 $2$ 次操作，对第 $1$ 到 $7$ 道菜做思考实验。最多能为 $1$ 位客人提供套餐，答案为 $1$。 - 第 $3$ 次操作，将第 $5$ 到 $7$ 道菜的美味度全部变为 $2$。此时美味度为 $(1, 2, 3, 4, 2, 2, 2, 3, 4, 5)$。 - 第 $4$ 次操作，为第 $5$ 到 $7$ 道菜加配料。美味度变为 $(1, 2, 3, 4, 3, 3, 3, 3, 4, 5)$。 - 第 $5$ 次操作，为第 $5$ 到 $7$ 道菜加配料。美味度变为 $(1, 2, 3, 4, 4, 4, 4, 3, 4, 5)$。 - 第 $6$ 次操作，为第 $5$ 到 $7$ 道菜加配料。美味度变为 $(1, 2, 3, 4, 5, 5, 5, 3, 4, 5)$。 - 第 $7$ 次操作，对第 $1$ 到 $10$ 道菜做思考实验。最多能为 $1$ 位客人提供套餐，答案为 $1$。 - 第 $8$ 次操作，将第 $6$ 到 $7$ 道菜的美味度全部变为 $2$。美味度变为 $(1, 2, 3, 4, 5, 2, 2, 3, 4, 5)$。 - 第 $9$ 次操作，将第 $6$ 道菜的美味度变为 $1$。美味度变为 $(1, 2, 3, 4, 5, 1, 2, 3, 4, 5)$。 - 第 $10$ 次操作，对第 $1$ 到 $10$ 道菜做思考实验。最多可为 $2$ 位客人提供套餐，答案为 $2$。 ### 数据范围 - $1 \leq N, Q \leq 150000$ - $1 \leq K \leq 5$ - $1 \leq D_i \leq K \ (1 \leq i \leq N)$ - $T_i \in \{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$ - 所有输入均为整数。 由 ChatGPT 5 翻译