AT_abc356_f [ABC356F] Distance Component Size Query

题目描述

给定一个整数 $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

输入 #1

7 5
1 3
1 10
2 3
1 7
2 3
1 10
2 3

输出 #1

1
3
2

输入输出样例 #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

10

输入输出样例 #3

输入 #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 翻译