CF1758F Decent Division

一个二进制字符串是指每个字符都是 $ \texttt{0} $ 或 $ \texttt{1} $ 的字符串。如果一个二进制字符串中 $ \texttt{0} $ 和 $ \texttt{1} $ 的数量相等，则称其为“良好”二进制字符串。 最初，你有一个无限长的二进制字符串 $ t $，其所有字符均为 $ \texttt{0} $。你将得到一个长度为 $ n $ 的更新序列 $ a $，其中 $ a_i $ 表示将下标为 $ a_i $ 的字符翻转（$ \texttt{0} \leftrightarrow \texttt{1} $）。你需要在每次更新后维护并修改一个不相交区间的集合 $ S $，使得： - 对于每个区间 $ [l,r] $，子串 $ t_l \dots t_r $ 是一个良好的二进制字符串； - 对于所有 $ t_i = \texttt{1} $ 的下标 $ i $，都存在某个 $ [l,r] \in S $，使得 $ l \leq i \leq r $。 你只需要在每次更新后输出被加入或移除的区间。你在所有操作中对 $ S $ 的区间添加与移除总次数最多只能有 $ \mathbf{10^6} $ 次。 更正式地，令 $ S_i $ 表示第 $ i $ 次更新后的区间集合，初始 $ S_0 = \varnothing $（空集）。定义 $ X_i $ 为第 $ i $ 次更新后被移除的区间集合，$ Y_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 $，表示本次更新后需要从 $ 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 $。 所有更新操作中移除和加入的区间总数不得超过 $ \mathbf{10^6} $。 在每次更新后，$ S $ 中的所有区间应两两不相交，并且覆盖所有值为 $ 1 $ 的位置。 可以证明，在这些约束下总是存在解。

样例中的换行仅为便于阅读，输出时无需特意换行。 第一次更新后，$ 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} $。 由 ChatGPT 4.1 翻译