[AdditionalFile5633.zip](file://AdditionalFile5633.zip?type=additional_file)

#5633. 「USACO 2026 Third Platinum」Min Max Subarrays II

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2026 Third Contest, Platinum Problem 3. Min Max Subarrays II

给定整数 $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$ 个 $0$ 到 $10^9$ 之间的整数组成的数组 $a$，使得对于所有的 $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

输入

3
2 2
1 1 2 1
1 1 2 2
2 2
1 1 2 1
1 2 2 2
4 1
2 2 4 3

输出

-1
1 2
0 3 0 0

在第一个测试用例中，答案为 $-1$，因为数组的最小值不能同时既是 $1$ 又是 $2$。

在第二个测试用例中，样例输出中的 $a[1 \dots 2]$ 在 $a[1]$ 处取得最小值 $1$，满足第一个限制。由于 $a[2] = 2$，第二个限制也得到了满足。

在第三个测试用例中，存在多个解。例如，数组 $[4, 3, 2, 1]$ 也是正确的。

样例 2

输入

4
2 2
1 1 2 1
2 1 2 2
3 2
1 1 2 3
2 2 3 1
5 2
1 1 2 3
1 4 5 2
4 4
1 1 4 1
1 2 3 2
2 1 2 5
2 3 4 6

输出

1 2
-1
3 3 0 2 2
1 5 2 6

在第二个测试用例中，数组 $[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