Extending Set of Points
Contest: Educational Codeforces Round 62 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, divide and conquer, dsu

For a given set of two-dimensional points $$$S$$$, let's denote its extension $$$E(S)$$$ as the result of the following algorithm:

Create another set of two-dimensional points $$$R$$$, which is initially equal to $$$S$$$. Then, while there exist four numbers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ such that $$$(x_1, y_1) \in R$$$, $$$(x_1, y_2) \in R$$$, $$$(x_2, y_1) \in R$$$ and $$$(x_2, y_2) \notin R$$$, add $$$(x_2, y_2)$$$ to $$$R$$$. When it is impossible to find such four integers, let $$$R$$$ be the result of the algorithm.

Now for the problem itself. You are given a set of two-dimensional points $$$S$$$, which is initially empty. You have to process two types of queries: add some point to $$$S$$$, or remove some point from it. After each query you have to compute the size of $$$E(S)$$$.

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, each containing two integers $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le 3 \cdot 10^5$$$), denoting $$$i$$$-th query as follows: if $$$(x_i, y_i) \in S$$$, erase it from $$$S$$$, otherwise insert $$$(x_i, y_i)$$$ into $$$S$$$.

Output format:
Print $$$q$$$ integers. $$$i$$$-th integer should be equal to the size of $$$E(S)$$$ after processing first $$$i$$$ queries.

Constraints:
Time limit: 3.5 s
Memory limit: 1024.0 MB

Example input:
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1

Example output:
1 2 4 4 4 6 3

Editorial:
Let's try to analyze how the size of $$$E(S)$$$ can be calculated. Let's connect points having same $$$x$$$-coordinates to each other, and do the same for points having same $$$y$$$-coordinates. Then we can solve the problem for each component separatedly: after the algorithm is run, the component will contain the points $$$(X, Y)$$$ such that at least one point in the component has $$$x$$$-coordinate equal to $$$X$$$, and at least one point in the component (maybe same, maybe another one) has $$$y$$$-coordinate equal to $$$Y$$$. So the answer for each component is the product of the number of distinct $$$x$$$-coordinates and the number of distinct $$$y$$$-coordinates in the component.
Now we can process insertion queries: there are many ways to do it, but, in my opinion, the easiest way to handle them is to create a separate vertex for every $$$x$$$-coordinate and $$$y$$$-coordinate, and process each point as an edge connecting vertices corresponding to its coordinates (edges can be easily added by using DSU with rank heuristics).
To handle removals, we will get rid of them completely. Transform the input into a set of $$$O(q)$$$ events "some point exists from query $$$l$$$ to query $$$r$$$". Then build a segment tree over queries, and break each event into $$$O(\log q)$$$ segments with this segment tree. Then we can initialize a DSU, and run DFS on the vertices of the segment tree to get answers for all queries. When we enter some node, we add all edges that exist on the corresponding segment into DSU. If we are in a leaf node, we may compute the $$$E(S)$$$ for the corresponding query. And when we leave a vertex, we can rollback all changes we made when we entered it. One important moment is that using path compression in DSU here is meaningless since it doesn't work with rollbacks well.
This solution works in $$$O(q \log^2 q)$$$.