AT_agc056_c [AGC056C] 01 Balanced
题目描述
[problemUrl]: https://atcoder.jp/contests/agc056/tasks/agc056_c
考虑构造一个由 `0` 和 `1` 组成的长度为 $ N $ 的字符串 $ s $。其中 $ s $ 需要满足 $ M $ 个条件。第 $ i $ 个条件由整数 $ L_i, R_i $（$ 1 \leq L_i < R_i \leq N $）表示，这意味着在 $ s $ 的第 $ L_i $ 个字符到第 $ R_i $ 个字符之间，包含的 `0` 和 `1` 的数量必须相等。
请在所有满足条件的 $ s $ 中找出字典序最小的那个。可以证明，在问题的约束下，满足条件的 $ s $ 一定存在。
输入格式
输入通过标准输入给出，格式如下：
> $ N $ $ M $
> $ L_1 $ $ R_1 $
> $ L_2 $ $ R_2 $
> $ \vdots $
> $ L_M $ $ R_M $
输出格式
输出答案。
说明/提示
### 约束条件
- $ 2 \leq N \leq 10^6 $
- $ 1 \leq M \leq 200000 $
- $ 1 \leq L_i < R_i \leq N $
- $ (R_i - L_i + 1) \equiv 0 \pmod{2} $
- $ (L_i, R_i) \neq (L_j, R_j) $（$ i \neq j $）
- 输入中的所有值均为整数
翻译由 DeepSeek R1 完成