14234: 【原4234】希干希纳区夺还作战
题目
题目描述
author: 泰玛什 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4234
Background
希干希纳区夺还作战开始了。你，作为光荣的调查兵团的一员，身上肩负着人类的未来。
Description
我们将战场看做一个二位的网格图，在上面的一些位置，存在着奇行种巨人。
由于奇行种的行动方式非常诡异，对于\(x_1, x_2, y_1, y_2\)若\((x_1, y_1), (x_1, y_2), (x_2, y_1)\)位置都存在着奇行种，那么我们可以认为\((x_2, y_2)\)位置也存在奇行种巨人。
我们把每个奇行种巨人看做一个点，记观测到的所有奇行种的位置集合为\(S\)。根据上述推测方法，我们可以得到一个推测的奇行种位置集合\(E(S)\)。
一开始，战场上没有任何的奇行种。每一时刻，会有一位置\((x_i, y_i)\)发出信号，若该位置不在\(S\)中，则将其加入；反之，将其从\(S\)中删除。
请你给出每个时刻的战场危险程度，即\(E(S)\)集合大小。
Input Format
第一行有一个整数\(q\)，表示接下来的时刻数。
接下来\(q\)行，每行两个数\(x_i, y_i\)，含义如上所示。
Output Format
输出共一行，\(q\)个数分布表示每一时刻\(E(S)\)集合的大小。
Sample Input
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
Sample Output
1 2 4 4 4 6 3
Limit
-
对于40%的数据，\(1 \leq q \leq 10^3\)，且任意时刻\(1 \leq |E(S)| \leq 10^3\)。
-
对于另外30%的数据，每一时刻只会向S中新加入位置，没有删除操作。
-
对于100%的数据，保证\(1 \leq q \leq 10^5, 1 \leq x_i, y_i \leq 10^5\)。
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！