Decent Division
Contest: Codeforces Round 836 (Div. 2)
Difficulty rating: 3000
Tags: constructive algorithms, data structures

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$$$.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
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}$$$.

Example input:
5
1
6
5
5
6

Example output:
0
1
1 2

0
1
5 6

1
5 6
2
6 7
4 5

1
4 5
0

1
6 7
0

Editorial:
After each update, we want to maintain the invariant that each interval is balanced, and additionally that there is a gap containing at least one zero in between each pair of consecutive intervals. Since every $$$\texttt{1}$$$ must be contained in an interval, this is equivalent to having non-empty gaps between consecutive intervals after an update.
There are several cases we need to handle.
• Case 1: Bit $$$a_i$$$ is changed from $$$\texttt{0}$$$ to $$$\texttt{1}$$$.   Case 1a: Bit $$$a_i$$$ is contained in an interval after the previous updateIf we are inside an interval, then we want to grow the interval that contains it by 2 zeros to maintain balance. If the interval containing $$$a_i$$$ is $$$[l, r]$$$, then we can expand it to $$$[l, r + 1]$$$. Since there is at least one $$$\texttt{0}$$$ after each interval, $$$a_{r + 1} = 0$$$, so this contains one of the two zeroes we need.If there is another interval $$$r + 2 \in [l', r']$$$, then increasing the right bound again by 1 would overlap with this interval. In this case, We know that $$$a_{r' + 1} = 0$$$ as well, so we can merge both intervals together into $$$[l, r' + 1]$$$ to get a total of two new zeros. $$$[l', r']$$$ was also previously balanced, so the interval is still balanced. In this case, we removed two intervals and added one interval, so a total of three operations were used.If there is no intervals where $$$r + 2 \in [l', r']$$$, then $$$a_{r + 2} = 0$$$, so we can simply expand the current interval once more to $$$[l, r + 2]$$$. One interval was removed and one interval was added, so a total of two operations were used. Case 1b: Bit $$$a_i$$$ is not contained in an interval.If there exists an interval where $$$i + 1 \in [i + 1, r]$$$, then we can expand it to $$$[k, r + 1]$$$. This interval is directly after $$$a_i$$$, so expanding it by one to the left will include an extra $$$\texttt{1}$$$. $$$a_{r + 1} = 0$$$ since it is part of the gap between two intervals, so including it balances $$$a_i$$$. One interval was removed and one interval was added, so a total of two operations were used.If there is no interval where $$$i + 1 \in [i + 1, r]$$$, then $$$a_{i + 1} = 0$$$. Therefore, we can simply add $$$[i, i + 1]$$$, which is balanced. One interval was added, so a total of one operation was used. In both cases, after adding a new interval to the set, we can merge with any adjacent intervals to the left or right. This will maintain the invariant that there is a gap between consecutive ranges as mentioned earlier. We merge at most once to the left and one to the right. Since the maximum number of operations done earlier is 3, the maximum number of operations in total is 5 in this case.
• Case 1a: Bit $$$a_i$$$ is contained in an interval after the previous updateIf we are inside an interval, then we want to grow the interval that contains it by 2 zeros to maintain balance. If the interval containing $$$a_i$$$ is $$$[l, r]$$$, then we can expand it to $$$[l, r + 1]$$$. Since there is at least one $$$\texttt{0}$$$ after each interval, $$$a_{r + 1} = 0$$$, so this contains one of the two zeroes we need.If there is another interval $$$r + 2 \in [l', r']$$$, then increasing the right bound again by 1 would overlap with this interval. In this case, We know that $$$a_{r' + 1} = 0$$$ as well, so we can merge both intervals together into $$$[l, r' + 1]$$$ to get a total of two new zeros. $$$[l', r']$$$ was also previously balanced, so the interval is still balanced. In this case, we removed two intervals and added one interval, so a total of three operations were used.If there is no intervals where $$$r + 2 \in [l', r']$$$, then $$$a_{r + 2} = 0$$$, so we can simply expand the current interval once more to $$$[l, r + 2]$$$. One interval was removed and one interval was added, so a total of two operations were used.
• Case 1b: Bit $$$a_i$$$ is not contained in an interval.If there exists an interval where $$$i + 1 \in [i + 1, r]$$$, then we can expand it to $$$[k, r + 1]$$$. This interval is directly after $$$a_i$$$, so expanding it by one to the left will include an extra $$$\texttt{1}$$$. $$$a_{r + 1} = 0$$$ since it is part of the gap between two intervals, so including it balances $$$a_i$$$. One interval was removed and one interval was added, so a total of two operations were used.If there is no interval where $$$i + 1 \in [i + 1, r]$$$, then $$$a_{i + 1} = 0$$$. Therefore, we can simply add $$$[i, i + 1]$$$, which is balanced. One interval was added, so a total of one operation was used.
• Case 2: Bit $$$a_i$$$ is changed from $$$\texttt{1}$$$ to $$$\texttt{0}$$$. Suppose that $$$i \in [l, r]$$$. In this case, we want to somehow split the interval into two balanced portions. Now, suppose we compute the prefix sums of the balance, where $$$\texttt{0}$$$ corresponds to $$$-1$$$ and $$$\texttt{1}$$$ corresponds to $$$+1$$$. If $$$x$$$ is the first location where the prefix sum equals $$$-2$$$, then we claim that we can split the interval into $$$[l, x - 2]$$$ and $$$[x + 1, r]$$$.To prove this, note that the balance of the empty prefix is 0, so before the prefix sum equals $$$-2$$$ for the first time, it must have gone $$$..., 0, -1, -2$$$. To have two decreases in a row, we must have $$$a_{x - 1} = a_x = 0$$$. In the interval $$$[l, x - 2]$$$, the final balance prefix sum is $$$0$$$, so the first interval is balanced. Since we changed a $$$\texttt{1}$$$ to a $$$\texttt{1}$$$ and removed two $$$\texttt{0}$$$s, the first interval being balanced implies that the second interval is balanced as well. In addition, since the original interval satisfied the separation invariant, and the new intervals are separated by two $$$\texttt{0}$$$s, the separation invariant is still satisfied.To compute the first time when the balance prefix sum equals -2, we can use binary search on the interval using a lazy segment tree. The segment tree represents a global balance prefix sum, and we can range query the minimum balance on an interval. We can binary search for the lowest index on the interval where the minimum prefix sum is less than -2.In this case, we removed one interval and added two new intervals, for a total of three operations.
In both cases, we use at most 5 operations in a single step, so we in total use at most $$$5n$$$ operations, which fits in our bound. In practice, this upper bound is quite loose.
Because of the binary search on the lazy segment tree, the time complexity for this solution is $$$O(n \log^2 n)$$$. Note that this can be optimized to $$$O(n \log n)$$$ by optimizing the binary search, but this was not required.