← 返回题目列表

Codeforces · 1140/F

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$$$ 个查询,如下所示: if $$$(x_i, y_i) \in S$$$,将其删除来自$$$S$$$,否则将$$$(x_i, y_i)$$$插入$$$S$$$。

输出

打印 $$$q$$$ 整数。第 $$$i$$$ 个整数应等于处理第一个 $$$i$$$ 查询后 $$$E(S)$$$ 的大小。

示例

输入 #1

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

输出 #1

1 2 4 4 4 6 3