AT_abc216_g [ABC216G] 01Sequence

题目描述

考虑一个只包含 0 和 1 的长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$，满足以下条件：

对于所有 $i=1,2,\dots,M$，区间 $A_{L_i}, A_{L_i+1},\dots,A_{R_i}$ 中包含的 1 的个数不少于 $X_i$ 个。

请输出满足条件的数列 $A$ 中，1 的个数最少的一个方案。

在给定的约束下，必定存在至少一个满足条件的数列 $A$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$

$L_1$ $R_1$ $X_1$

$L_2$ $R_2$ $X_2$

$\vdots$

$L_M$ $R_M$ $X_M$

输出格式

请输出一个只包含 0 和 1 的数列 $A$，用空格分隔。

$A_1$ $A_2$ $\dots$ $A_N$

数列 $A$ 必须满足所有给定的条件。

输入输出样例 #1

输入 #1

6 3
1 4 3
2 2 1
4 6 2

输出 #1

0 1 1 1 0 1

输入输出样例 #2

输入 #2

8 2
2 6 1
3 5 3

输出 #2

0 0 1 1 1 0 0 0

说明/提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq \min(2 \times 10^5, \frac{N(N+1)}{2})$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq X_i \leq R_i-L_i+1$
• 如果 $i \neq j$，则 $(L_i,R_i) \neq (L_j,R_j)$
• 所有输入均为整数

样例说明 1

如 1 1 0 1 1 0 等答案也是正确的。像 0 1 1 1 1 1 这样的答案由于没有最小化 1 的数量，因此不正确。

由 ChatGPT 4.1 翻译