Decent Division

题意翻译

对于一个 $01$ 串，定义它是好的，当且仅当里面 $0,1$ 数量相等。 现在有一个无限长的字符串，初始全部位置都是 $0$，有 $m$ 次操作，每次操作给定下标 $w$ 并翻转 $w$ 这个位置的字符 $(0\to 1,1\to 0)$。 每次操作完后，你需要构造一个由若干个不交区间组成的集合 $S$ 满足任意一个区间对应的字串是好的，并且任意一个 $1$ 都在某个区间中。 具体的，每次操作完，你需要从原有的集合中加入或删除一些区间，使得新的集合符合条件。 你需要保证操作次数在 $10^6$ 以内。

题目描述

A binary string is a string where every character is $ \texttt{0} $ or $ \texttt{1} $ . Call a binary string decent if it has an equal number of $ \texttt{0} $ s and $ \texttt{1} $ s. Initially, you have an infinite binary string $ t $ whose characters are all $ \texttt{0} $ s. You are given a sequence $ a $ of $ n $ updates, where $ a_i $ indicates that the character at index $ a_i $ will be flipped ( $ \texttt{0} \leftrightarrow \texttt{1} $ ). You need to keep and modify after each update a set $ S $ of disjoint ranges such that: - for each range $ [l,r] $ , the substring $ t_l \dots t_r $ is a decent binary string, and - for all indices $ i $ such that $ t_i = \texttt{1} $ , there exists $ [l,r] $ in $ S $ such that $ l \leq i \leq r $ . You only need to output the ranges that are added to or removed from $ S $ after each update. You can only add or remove ranges from $ S $ at most $ \mathbf{10^6} $ times. More formally, let $ S_i $ be the set of ranges after the $ i $ -th update, where $ S_0 = \varnothing $ (the empty set). Define $ X_i $ to be the set of ranges removed after update $ i $ , and $ Y_i $ to be the set of ranges added after update $ i $ . Then for $ 1 \leq i \leq n $ , $ S_i = (S_{i - 1} \setminus X_i) \cup Y_i $ . The following should hold for all $ 1 \leq i \leq n $ : - $ \forall a,b \in S_i, (a \neq b) \rightarrow (a \cap b = \varnothing) $ ; - $ X_i \subseteq S_{i - 1} $ ; - $ (S_{i-1} \setminus X_i) \cap Y_i = \varnothing $ ; - $ \displaystyle\sum_{i = 1}^n {(|X_i| + |Y_i|)} \leq 10^6 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of updates. The next $ n $ lines each contain a single integer $ a_i $ ( $ 1 \leq a_i \leq 2 \cdot 10^5 $ ) — the index of the $ i $ -th update to the string.

输出格式

After the $ i $ -th update, first output a single integer $ x_i $ — the number of ranges to be removed from $ S $ after update $ i $ . In the following $ x_i $ lines, output two integers $ l $ and $ r $ ( $ 1 \leq l < r \leq 10^6 $ ), which denotes that the range $ [l,r] $ should be removed from $ S $ . Each of these ranges should be distinct and be part of $ S $ . In the next line, output a single integer $ y_i $ — the number of ranges to be added to $ S $ after update $ i $ . In the following $ y_i $ lines, output two integers $ l $ and $ r $ ( $ 1 \leq l < r \leq 10^6 $ ), which denotes that the range $ [l,r] $ should be added to $ S $ . Each of these ranges should be distinct and not be part of $ S $ . The total number of removals and additions across all updates must not exceed $ \mathbf{10^6} $ . After processing the removals and additions for each update, all the ranges in $ S $ should be disjoint and cover all ones. It can be proven that an answer always exists under these constraints.

输入输出样例

输入样例 #1

5
1
6
5
5
6

输出样例 #1

0
1
1 2

0
1
5 6

1
5 6
2
6 7
4 5

1
4 5
0

1
6 7
0

说明

Line breaks are provided in the sample only for the sake of clarity, and you don't need to print them in your output. After the first update, the set of indices where $ a_i = 1 $ is $ \{1\} $ . The interval $ [1, 2] $ is added, so $ S_1 = \{[1, 2]\} $ , which has one $ \texttt{0} $ and one $ \texttt{1} $ . After the second update, the set of indices where $ a_i = 1 $ is $ \{1, 6\} $ . The interval $ [5, 6] $ is added, so $ S_2 = \{[1, 2], [5, 6]\} $ , each of which has one $ \texttt{0} $ and one $ \texttt{1} $ . After the third update, the set of indices where $ a_i = 1 $ is $ \{1, 5, 6\} $ . The interval $ [5, 6] $ is removed and the intervals $ [4, 5] $ and $ [6, 7] $ are added, so $ S_3 = \{[1, 2], [4, 5], [6, 7]\} $ , each of which has one $ \texttt{0} $ and one $ \texttt{1} $ . After the fourth update, the set of indices where $ a_i = 1 $ is $ \{1, 6\} $ . The interval $ [4, 5] $ is removed, so $ S_4 = \{[1, 2], [6, 7]\} $ , each of which has one $ \texttt{0} $ and one $ \texttt{1} $ . After the fifth update, the set of indices where $ a_i = 1 $ is $ \{1\} $ . The interval $ [6, 7] $ is removed, so $ S_5 = \{[1, 2]\} $ , which has one $ \texttt{0} $ and one $ \texttt{1} $ .

**题意翻译**

对于一个由0和1组成的字符串，如果0和1的数量相等，则称这个字符串是好的。

现在有一个无限长的字符串，初始时所有的字符都是0。有m次操作，每次操作给出一个下标w，并翻转这个位置的字符（0变成1，1变成0）。

每次操作之后，你需要构造一个由若干个不重叠区间组成的集合S，使得集合中任意区间的子串都是好的，并且所有的1都必须包含在某个区间中。

具体来说，每次操作后，你需要从原有的集合中添加或删除一些区间，使得新的集合符合条件。

你需要在操作次数不超过$10^6$的前提下保证这一点。

**题目描述**

一个二进制字符串是一个每个字符都是0或1的字符串。如果一个二进制字符串中0和1的数量相等，则称这个字符串是好的。

最初，你有一个全为0的无穷长二进制字符串t。给你一个长度为n的更新序列a，其中$a_i$表示字符串t中下标为$a_i$的字符将被翻转（0和1互换）。在每次更新后，你需要维护一个由不重叠区间组成的集合S，使得：

- 对于集合S中的每个区间$[l, r]$，子字符串$t_l \dots t_r$是一个好的二进制字符串；
- 对于所有满足$t_i = \texttt{1}$的下标i，存在S中的某个区间$[l, r]$使得$l \leq i \leq r$。

你只需要输出每次更新后从S中添加或删除的区间。你可以在不超过$10^6$次的情况下从S中添加或删除区间。

更形式化地说，设$S_i$是第i次更新后的区间集合，其中$S_0 = \varnothing$（空集）。定义$X_i$为第i次更新后从集合中删除的区间集合，$Y_i$为第i次更新后添加到集合中的区间集合。那么对于所有$1 \leq i \leq n$，有$S_i = (S_{i - 1} \setminus X_i) \cup Y_i$。对于所有$1 \leq i \leq n$，以下条件必须成立：

- 对于任意的a, b属于$S_i$，如果a不等于b，则a和b没有交集；
- $X_i$是$S_{i - 1}$的子集；
- $(S_{i-1} \setminus X_i) \cap Y_i = \varnothing$；
- $\displaystyle\sum_{i = 1}^n {(|X_i| + |Y_i|)} \leq 10^6$。

**输入输出格式**

**输入格式**

第一行包含一个整数$n$（$1 \leq n \leq 2 \cdot 10^5$）——更新的次数。

接下来n行，每行包含一个整数$a_i$（$1 \leq a_i \leq 2 \cdot 10^5$）——第i次更新的字符串下标。

**输出格式**

在第i次更新后，首先输出一个整数$x_i$——表示从S中删除的区间数量。

在接下来的$x_i$行中，输出两个整数$l$和$r$（$1 \leq l < r \leq 10^6$），表示应该从S中删除的区间$[l, r]$。这些区间应该是不同的，并且是S的一部分。

在下一行中，输出一个整数$y_i$——表示应该添加到S中的区间数量。

在接下来的$y_i$行中，输出两个整数$l$和$r$（$1 \leq l < r \leq 10^6$），表示应该添加到S中的区间$[l, r]$。这些区间应该是不同的，并且不是S的一部分。

所有更新中删除和添加的总次数不得超过$10^6$。

在处理完每次更新的删除和添加后，S中的所有区间都应该是互不重叠的，并且覆盖所有的1。

可以证明，在这些约束条件下，总是存在一个答案。**题意翻译** 对于一个由0和1组成的字符串，如果0和1的数量相等，则称这个字符串是好的。 现在有一个无限长的字符串，初始时所有的字符都是0。有m次操作，每次操作给出一个下标w，并翻转这个位置的字符（0变成1，1变成0）。 每次操作之后，你需要构造一个由若干个不重叠区间组成的集合S，使得集合中任意区间的子串都是好的，并且所有的1都必须包含在某个区间中。 具体来说，每次操作后，你需要从原有的集合中添加或删除一些区间，使得新的集合符合条件。 你需要在操作次数不超过$10^6$的前提下保证这一点。 **题目描述** 一个二进制字符串是一个每个字符都是0或1的字符串。如果一个二进制字符串中0和1的数量相等，则称这个字符串是好的。 最初，你有一个全为0的无穷长二进制字符串t。给你一个长度为n的更新序列a，其中$a_i$表示字符串t中下标为$a_i$的字符将被翻转（0和1互换）。在每次更新后，你需要维护一个由不重叠区间组成的集合S，使得： - 对于集合S中的每个区间$[l, r]$，子字符串$t_l \dots t_r$是一个好的二进制字符串； - 对于所有满足$t_i = \texttt{1}$的下标i，存在S中的某个区间$[l, r]$使得$l \leq i \leq r$。 你只需要输出每次更新后从S中添加或删除的区间。你可以在不超过$10^6$次的情况下从S中添加或删除区间。 更形式化地说，设$S_i$是第i次更新后的区间集合，其中$S_0 = \varnothing$（空集）。定义$X_i$为第i次更新后从集合中删除的区间集合，$Y_i$为第i次更新后添加到集合中的区间集合。那么对于所有$1 \leq i \leq n$，有$S_i = (S_{i - 1} \setminus X_i) \cup Y_i$。对于所有$1 \leq i \leq n$，以下条件必须成立： - 对于任意的a, b属于$S_i$，如果a不等于b，则a和b没有交集； - $X_i$是$S_{i - 1}$的子集； - $(S_{i-1} \setminus X_i) \cap Y_i = \varnothing$； - $\displaystyle\sum_{i = 1}^n {(|X_i| + |Y_i|)} \leq 10^6$。 **输入输出格式** **输入格式** 第一行包含一个整数$n$（$1 \leq n \leq 2 \cdot 10^5$）——更新的次数。 接下来n行，每行包含一个整数$a_i$（$1 \leq a_i \leq 2 \cdot 10^5$）——第i次更新的字符串下标。 **输出格式** 在第i次更新后，首先输出一个整数$x_i$——表示从S中删除的区间数量。 在接下来的$x_i$行中，输出两个整数$l$和$r$（$1 \leq l < r \leq 10^6$），表示应该从S中删除的区间$[l, r]$。这些区间应该是不同的，并且是S的一部分。 在下一行中，输出一个整数$y_i$——表示应该添加到S中的区间数量。 在接下来的$y_i$行中，输出两个整数$l$和$r$（$1 \leq l < r \leq 10^6$），表示应该添加到S中的区间$[l, r]$。这些区间应该是不同的，并且不是S的一部分。 所有更新中删除和添加的总次数不得超过$10^6$。 在处理完每次更新的删除和添加后，S中的所有区间都应该是互不重叠的，并且覆盖所有的1。 可以证明，在这些约束条件下，总是存在一个答案。