[ABC216G] 01Sequence
题意翻译
你需要构造出一个长度为 $n$ 的 $01$ 序列，满足 $m$ 个限制 $(l_i,r_i,x_i)$：在 $[l_i,r_i]$ 这段区间内，序列上 $1$ 的个数不小于 $x_i$。**你需要保证你的方案中包含 $1$ 的个数最小。**
数据保证有解。
$1 \le n,m \le 2 \times 10^5$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc216/tasks/abc216_g
`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` の数が**最も少ない**例を $ 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
6 3
1 4 3
2 2 1
4 6 2输出样例 #1
0 1 1 1 0 1输入样例 #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) $
- 入力は全て整数
### Sample Explanation 1
`1 1 0 1 1 0` などの答えも正解です。 `0 1 1 1 1 1` などの答えは含まれる `1` の数が最小化されていないので、不正解です。