CF2157C.Meximum Array 2

给定三个正整数 $n$、$k$ 和 $q$。你还会得到 $q$ 个三元组 $(c, l, r)$，其中 $1 \leq c \leq 2$，$1 \leq l \leq r \leq n$。

如果存在一个数组 $a_1, a_2, \ldots, a_n$ 满足 $0 \leq a_i \leq 10^9$ 对于每个 $i \in [1, n]$，并且对于每个给定的三元组 $(c, l, r)$，都有以下条件成立：

• 如果 $c = 1$，则 $\min(a_l, a_{l+1}, \ldots, a_r) = k$；
• 如果 $c = 2$，则 $\operatorname{MEX}^* (a_l, a_{l+1}, \ldots, a_r) = k$。

注意，所有约束中的参数 $k$ 都是相同的。

找到一个“meximum”数组 $a_1, a_2, \ldots, a_n$，长度为 $n$。输入保证总存在一个合法的数组。如果有多种满足条件的数组，你可以输出其中任意一种。

$^*$ 最小未出现数（MEX），指对一组整数 $a_1, a_2, \ldots, a_k$，它们的 MEX 定义为没有出现在该集合中的最小非负整数 $x$。

每组测试包含若干组测试用例。第一行包含测试用例数量 $t$，$1 \le t \le 500$。每组测试用例的描述如下。

每组测试用例的第一行包含三个整数 $n$、$k$、$q$，$1 \leq k \leq n \leq 100$，$1 \leq q \leq 100$——表示数组的长度 $a_1, a_2, \ldots, a_n$，$\min$ 和 $\operatorname{MEX}$ 约束的目标值 $k$，以及约束的数量 $q$。

接下来 $q$ 行，每行包含一个三元组 $(c, l, r)$，对数组 $a_{l}, a_{l+1}, ..., a_{r}$ 加以约束。含义如上所述。

保证输入对应的每组情况下都至少存在一个合法数组。

注意，不存在 $n$、$k$ 或 $q$ 在所有测试用例的总和上的其他限制。

对于每组测试用例，输出一行，包含一个合法的“meximum”数组 $a_1, a_2, \ldots, a_n$。

在第一个测试用例中，需要构造一个 $n=6$，$k=2$，有 $q=2$ 个约束的 meximum 数组。

• 三元组 $(1, 1, 3)$：要求 $\min(a_1, a_2, a_3) = 2$；
• 三元组 $(2, 2, 6)$：要求 $\operatorname{MEX}(a_2, a_3, a_4, a_5, a_6) = 2$。

一个满足所有条件的数组，例如 $[2, 5, 4, 3, 0, 1]$。

在第二个测试用例中，需要构造一个 $n=3$，$k=3$，有一个约束的 meximum 数组。

• 三元组 $(2, 1, 3)$：要求 $\operatorname{MEX}(a_1, a_2, a_3) = 3$。

一个合法的数组是 $[2, 0, 1]$。

由 ChatGPT 5 翻译