P15581 [USACO26FEB] Min Max Subarrays II P

给定整数 $N, Q$（$1 \leq N, Q \leq 2 \cdot 10^5$）以及 $Q$ 个约束条件，每个约束由四个整数 $t_i, l_i, r_i, k_i$ 表示（$1 \leq t_i \leq 2$，$1 \leq l_i \leq r_i \leq N$，$0 \leq k_i \leq 10^9$，所有 $k_i$ 互不相同）。 构造一个由 $N$ 个整数组成的数组 $a$，每个整数在 $0$ 到 $10^9$ 之间，使得对于所有 $1 \leq i \leq Q$，如果 $t_i = 1$ 则 $\min a[l_i \dots r_i] = k_i$，如果 $t_i = 2$ 则 $\max a[l_i \dots r_i] = k_i$。如果存在多个有效的数组，输出任意一个。如果不存在有效的数组，输出 $-1$。

第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示独立测试用例的数量。 对于每个测试用例，第一行包含两个整数 $N, Q$。 接下来 $Q$ 行每行包含 4 个整数 $t_i$、$l_i$、$r_i$、$k_i$。 保证所有测试用例的 $N$ 之和以及 $Q$ 之和均不超过 $2 \cdot 10^5$。

对于每个测试用例，如果存在有效的数组，则在新的一行输出 $N$ 个空格分隔的整数 $a_1 \dots a_N$。否则，输出 $-1$。

#### 样例 1 解释 在第一个测试用例中，答案是 $-1$，因为数组的最小值不能同时是 $1$ 和 $2$。 在第二个测试用例中，在样例输出中，$a[1 \dots 2]$ 的最小值为 $a[1]$ 处的 $1$，满足第一个约束。由于 $a[2] = 2$，第二个约束也满足。 在第三个测试用例中，存在多个解。例如，数组 $[4, 3, 2, 1]$ 也可接受。 #### 样例 2 解释 在第二个测试用例中，数组 $[3, 5, 1]$ 满足第一个约束但不满足第二个约束。相反，数组 $[3, 1, 1]$ 满足第二个约束但不满足第一个约束。可以证明没有任何数组能同时满足这两个约束，因此答案是 $-1$。 对于所有其他测试用例，可以证明构造的数组满足所有 $Q$ 个约束。 ### 评分标准 - 输入 3-4：$N, Q \le 100$ 且同一测试用例内的所有 $t_i$ 相等 - 输入 5-6：同一测试用例内的所有 $t_i$ 相等 - 输入 7-10：$N, Q \le 100$ - 输入 11-14：无额外限制 题目来源：Charlie Yang 翻译由 DeepSeek 完成