Distance Component Size Query

题目描述

你被给定一个整数 $K$。对于一个最初为空的集合 $S$，按顺序处理 $Q$ 个以下两类查询：

$1 x$：给定一个整数 $x$。如果 $x$ 在 $S$ 中，则从 $S$ 中移除 $x$。否则，将 $x$ 加入 $S$。 $2 x$：给定一个在 $S$ 中的整数 $x$。考虑一个图，顶点是 $S$ 中的数，当且仅当两数的绝对差不超过 $K$ 时在它们之间存在一条边。打印包含 $x$ 的连通分量中的顶点个数。

输入格式

输入从标准输入按如下格式给出： $Q$ $K$ $\mathrm{query}_1$ $\vdots$ $\mathrm{query}_Q$

每个查询按如下格式给出： $1$ $x$

$2$ $x$

输出格式

处理这些查询。

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

1
3
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

10

8 0
1 1
1 2
2 1
1 1
1 2
1 1
1 2
2 1

1
1

提示

$1 \leq Q \leq 2\times 10^5$ $0 \leq K \leq 10^{18}$ 对于每个查询，$1 \leq x \leq 10^{18}$。 对于每个第二类查询，所给的 $x$ 在该时刻位于 $S$ 中。 所有输入值均为整数。查询处理过程如下：

在第一条查询中，将 $3$ 加入 $S$，得到 $S=\{3\}$。 在第二条查询中，将 $10$ 加入 $S$，得到 $S=\{3,10\}$。 在第三条查询中，考虑顶点为 $3$ 和 $10$ 且没有边的图。包含 $3$ 的连通分量大小为 $1$，因此输出 $1$。 在第四条查询中，将 $7$ 加入 $S$，得到 $S=\{3,7,10\}$。 在第五条查询中，考虑顶点为 $3,7,10$ 的图，边为 $3$ 与 $7$ 之间、以及 $7$ 与 $10$ 之间。包含 $3$ 的连通分量大小为 $3$，因此输出 $3$。 在第六条查询中，将 $10$ 从 $S$ 中移除，得到 $S=\{3,7\}$。 在第七条查询中，考虑顶点为 $3$ 和 $7$ 的图，二者之间有一条边。包含 $3$ 的连通分量大小为 $2$，因此输出 $2$。

标签: AtCoder|abc356F

来源

AtCoder|abc356F