Codeforces Round 836 (Div. 2) |
---|
Закончено |
Бинарной строкой называется строка, каждый символ которой это $$$\texttt{0}$$$ или $$$\texttt{1}$$$. Назовем бинарную строку приличной, если в ней поровну символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.
Изначально у вас есть бесконечная бинарная строка $$$t$$$, все символы которой равны $$$\texttt{0}$$$. Вам дана последовательность целых чисел $$$a$$$ из $$$n$$$ обновлений, где $$$a_i$$$ означает, что символ на позиции $$$a_i$$$ будет изменен на противоположный ($$$\texttt{0} \leftrightarrow \texttt{1}$$$). Вам нужно поддерживать и изменять после каждого обновления множество $$$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$$$ должно выполняться следующее:
Первая строка содержит одно целое число $$$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$$$ после обновления $$$i$$$.
В каждой из следующих $$$x_i$$$ строк выведите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq 10^6$$$), определяющие отрезок $$$[l,r]$$$, который должен быть удален из $$$S$$$. Каждый из этих отрезков должен быть уникальным и содержаться в $$$S$$$.обозначающее
В следующей строке выведите одно целое число $$$y_i$$$ — количество отрезков, которое нужно добавить в $$$S$$$ после обновления $$$i$$$.
В каждой из следующих $$$y_i$$$ строк выведите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq 10^6$$$), определяющие отрезок $$$[l,r]$$$, который должен быть добавлен в $$$S$$$. Каждый из этих отрезков должен быть уникальным и не содержаться в $$$S$$$.
Общее количество добавлений и удалений после всех обновлений не должно превосходить $$$\mathbf{10^6}$$$.
После каждого обновления после всех удалений и добавлений все отрезки в $$$S$$$ должны быть непересекающимися и покрывать все единицы.
Можно показать, что ответ всегда существует при данных ограничениях.
5 1 6 5 5 6
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}$$$.
Название |
---|