Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!