Extending Set of Points

题意翻译

定义一个点集合 $S=\{(x_i,y_i)\}(1\leq i\leq n)$ 的拓展操作为将符合以下条件的 $(x_0,y_0)$ 加入 $S$： - 存在 $a,b$，使得 $(a,b),(a,y_0),(x_0,b)\in S$。 不断执行以上操作直到不能操作，此时得到的集合即为拓展集合。现在给定 $q$ 个操作，每次加入或删除一个点，重复点即为删除，你需要输出每个操作之后的拓展集合大小（**不用真的拓展，只求大小**）。

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

7
1 1
1 2
2 1
2 2
1 2
1 3
2 1

输出样例 #1

1 2 4 4 4 6 3