AT_abc035_c.[ABC035C] オセロ

有 $N$ 个黑色面朝上的“奥赛罗”棋子，每个棋子的黑色面上写着 $0$，白色面上写着 $1$，它们被排成一行。之后，进行了 $Q$ 次操作，每次操作会将某个区间内的所有棋子翻面。具体来说，第 $i$ 次操作会将从左起第 $l_i$ 个到第 $r_i$ 个棋子全部翻面。

请你求出最终棋盘的状态。

输入从标准输入中给出，格式如下：

$N$ $Q$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

• 第 $1$ 行包含两个整数 $N,Q$，分别表示棋子的数量和操作的次数，$1 \leq N,Q \leq 200\,000$。
• 接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $l_i,r_i$，表示第 $i$ 次操作的区间，$1 \leq l_i \leq r_i \leq N$。

输出最终棋盘状态的字符串 $S$，$S$ 的第 $i$ 个字符表示从左起第 $i$ 个棋子上朝上的面的数字。请输出一行，不要忘记换行。

部分分

本题设有部分分。

• 对于满足 $1 \leq N,Q \leq 2\,000$ 的数据集，答对可得 $60$ 分。
• 对于无额外限制的数据集，答对可再得 $40$ 分，合计 $100$ 分。

样例解释 1

• 初始棋盘为 00000。
• 第 $1$ 次操作后，棋盘变为 11110。
• 第 $2$ 次操作后，棋盘变为 10001。
• 第 $3$ 次操作后，棋盘变为 10101。
• 第 $4$ 次操作后，棋盘变为 01010。
• 最终棋盘为 01010，这就是答案。
• 此样例满足部分分的限制。

样例解释 2

• 此样例满足部分分的限制。

由 ChatGPT 4.1 翻译