距离连通块大小查询

题目描述

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

1 x：给定整数 $x$。如果 $x$ 在 $S$ 中，则将 $x$ 从 $S$ 中移除；否则将 $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

查询的处理过程如下：

在第一个查询中，$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$。

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 \le Q \le 2\times 10^5$
• $0 \le K \le 10^{18}$
• 对于每个查询，$1 \le x \le 10^{18}$
• 对于每个第二种类型的查询，给出的 $x$ 在该时刻位于 $S$ 中
• 所有输入值均为整数