AT_abc356_f.[ABC356F] Distance Component Size Query

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数 $K$ 。对于初始为空的集合 $S$ ，依次处理 $Q$ 个如下两种类型的查询：

1 x：给定整数 $x$ 。如果 $S$ 中包含 $x$ ，则将 $x$ 从 $S$ 中移除；否则，将 $x$ 加入 $S$ 。
2 x：给定 $S$ 中的一个整数 $x$ 。以 $S$ 中的数为顶点，若两个数的差的绝对值不超过 $K$ ，则在它们之间连一条边。对于这样的图，输出 $x$ 所在连通分量的顶点数。

输入格式

输入按以下格式从标准输入给出。

$Q$ $K$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

每个查询的格式如下：

$1$ $x$

$2$ $x$

输出格式

请处理所有查询。

输入输出样例

输入#1
```
7 5
1 3
1 10
2 3
1 7
2 3
1 10
2 3
```
输出#1
```
1
3
2
```

输入#2

11 1000000000000000000
1 1
1 100
1 10000
1 1000000
1 100000000
1 10000000000
1 1000000000000
1 100000000000000
1 10000000000000000
1 1000000000000000000
2 1

输出#2

输入#3
```
8 0
1 1
1 2
2 1
1 1
1 2
1 1
1 2
2 1
```
输出#3
```
1
1
```

说明/提示

限制条件

$1 \leq Q \leq 2 \times 10^5$
$0 \leq K \leq 10^{18}$
对于每个查询， $1 \leq x \leq 10^{18}$
对于类型 $2$ 的查询，给定的 $x$ 一定在当前的 $S$ 中。
输入均为整数。

样例说明 1

查询的处理过程如下：

第 $1$ 个查询，将 $3$ 加入 $S$ ，此时 $S=\{3\}$ 。
第 $2$ 个查询，将 $10$ 加入 $S$ ，此时 $S=\{3,10\}$ 。
第 $3$ 个查询，考虑 $3,10$ 这两个顶点组成的图，没有边，输出 $3$ 所在连通分量的大小 $1$ 。
第 $4$ 个查询，将 $7$ 加入 $S$ ，此时 $S=\{3,7,10\}$ 。
第 $5$ 个查询，考虑 $3,7,10$ 这三个顶点组成的图， $3$ 和 $7$ 之间有边， $7$ 和 $10$ 之间有边，输出 $3$ 所在连通分量的大小 $3$ 。
第 $6$ 个查询，将 $10$ 从 $S$ 中移除， $S=\{3,7\}$ 。
第 $7$ 个查询，考虑 $3,7$ 这两个顶点组成的图， $3$ 和 $7$ 之间有边，输出 $3$ 所在连通分量的大小 $2$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页