Олимпиадный тренинг

Задача . F. Расширение множества точек


Для заданного множества точек на координатной плоскости \(S\) обозначим его расширение \(E(S)\) как результат следующего алгоритма:

Создадим другое множество точек \(R\), изначально равное \(S\). Затем, пока существуют четыре числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\), такие, что \((x_1, y_1) \in R\), \((x_1, y_2) \in R\), \((x_2, y_1) \in R\) и \((x_2, y_2) \notin R\), добавим \((x_2, y_2)\) к \(R\). Когда такую четверку чисел найти будет нельзя, прекратим алгоритм и скажем, что множество \(R\) — результат.

А теперь — сама задача. У вас есть множество \(S\), изначально пустое. Надо обрабатывать два типа запросов: добавить какую-нибудь точку в \(S\), или удалить точку. После каждого запроса выведите, чему равен размер множества \(E(S)\).

Входные данные

В первой строке задано одно целое число \(q\) (\(1 \le q \le 3 \cdot 10^5\)) — количество запросов.

Затем следуют \(q\) строк, в каждой из которых записаны два целых числа \(x_i\), \(y_i\) (\(1 \le x_i, y_i \le 3 \cdot 10^5\)), обозначающих \(i\)-й запрос следующим образом: если \((x_i, y_i) \in S\), удалить эту точку из \(S\), иначе вставить \((x_i, y_i)\) в \(S\).

Выходные данные

Выведите \(q\) целых чисел. \(i\)-е число должно быть равно размеру \(E(S)\) после первых \(i\) запросов.


Примеры
Входные данныеВыходные данные
1 7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
1 2 4 4 4 6 3

time 3500 ms
memory 1024 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя