← 返回题目列表

Codeforces · 1758/F

F. 体面的划分

中文机器翻译题面 查看原题

二进制字符串是每个字符为 $$$\texttt{0}$$$ 或 $$$\texttt{1}$$$ 的字符串。如果一个二进制字符串具有相同数量的 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$,则称该二进制字符串为正常字符串。

最初,您有一个无限二进制字符串 $$$t$$$,其字符均为 $$$\texttt{0}$$$s。您将获得 $$$n$$$ 更新的序列 $$$a$$$,其中 $$$a_i$$$ 表示索引 $$$a_i$$$ 处的字符将被翻转 ($$$\texttt{0} \leftrightarrow \texttt{1}$$$)。您需要在每次更新后保留并修改一组不相交的 $$$S$$$ 范围,以便:

- 对于每个范围 $$$[l,r]$$$,子字符串 $$$t_l \dots t_r$$$ 是一个不错的二进制字符串,并且
- 对于所有索引 $$$i$$$ 使得 $$$t_i = \texttt{1}$$$,在 $$$S$$$ 中存在 $$$[l,r]$$$ 使得 $$$l \leq i \leq r$$$。

您只需要输出每次更新后添加到 $$$S$$$ 或从 $$$S$$$ 中删除的范围。您最多只能在 $$$S$$$ 中添加或删除范围 $$$\mathbf{10^6}$$$ 次。

更正式地说,令 $$$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$$$:

- $$$\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$$$。

输入

第一行包含一个整数 $$$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$$$ — 更新 $$$i$$$ 后要从 $$$S$$$ 中删除的范围数。

在接下来的 $$$x_i$$$ 行中,输出两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l < r \leq 10^6$$$),这表示应从 $$$S$$$ 中删除 $$$[l,r]$$$ 范围。每个范围都应该是不同的,并且是 $$$S$$$ 的一部分。

在下一行中,输出单个整数 $$$y_i$$$ — 更新 $$$i$$$ 后要添加到 $$$S$$$ 的范围数。

在接下来的$$$y_i$$$行中,输出两个整数$$$l$$$和$$$r$$$ ($$$1 \leq l < r \leq 10^6$$$),这表示$$$[l,r]$$$范围应该添加到$$$S$$$上。每个范围都应该是不同的,并且不属于 $$$S$$$ 的一部分。

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

处理每次更新的删除和添加后,$$$S$$$ 中的所有范围应该是不相交的并覆盖所有范围。

可以证明在这些约束下答案总是存在的。

示例

输入 #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

注意

示例中提供换行符只是为了清楚起见,您不需要在输出中打印它们。

第一次更新后,$$$a_i = 1$$$ 的索引集为 $$$\{1\}$$$。添加了区间 $$$[1, 2]$$$,因此 $$$S_1 = \{[1, 2]\}$$$,其中有一个 $$$\texttt{0}$$$ 和一个 $$$\texttt{1}$$$。

第二次更新后,$$$a_i = 1$$$ 的索引集为$$$\{1, 6\}$$$。添加了区间$$$[5, 6]$$$,所以$$$S_2 = \{[1, 2], [5, 6]\}$$$,其中每一个都有一个$$$\texttt{0}$$$和一个$$$\texttt{1}$$$。

第三次更新后,$$$a_i = 1$$$ 的索引集为 $$$\{1, 5, 6\}$$$。去掉区间$$$[5, 6]$$$,增加区间$$$[4, 5]$$$和$$$[6, 7]$$$,所以$$$S_3 = \{[1, 2], [4, 5], [6, 7]\}$$$,每个区间有一个$$$\texttt{0}$$$和一个$$$\texttt{1}$$$。

第四次更新后,$$$a_i = 1$$$ 的索引集为$$$\{1, 6\}$$$。去掉了区间$$$[4, 5]$$$,所以$$$S_4 = \{[1, 2], [6, 7]\}$$$,其中每个都有一个$$$\texttt{0}$$$和一个$$$\texttt{1}$$$。

第五次更新后,$$$a_i = 1$$$ 的索引集为$$$\{1\}$$$。区间 $$$[6, 7]$$$ 被删除,因此 $$$S_5 = \{[1, 2]\}$$$,其中有一个 $$$\texttt{0}$$$ 和一个 $$$\texttt{1}$$$。