分数: 525 点
问题陈述
给你一个整数 K。对于一套 S 最初为空,进程 Q 按顺序查询以下两类: 给出了
1 x:整数 x 。如果 x 位于 S,删除 x 来自 S。否则,添加 x to S.2 x:整数 x 那是 给出了 S 。考虑一个图,其中顶点是中的数字 S,并且两个数字之间存在边缘当且仅当它们之间的绝对差最多为 K。打印包含以下内容的连接组件中的顶点数 x.
约束
- 1 \leq Q \leq 2\times 10^5
- 0 \leq K \leq 10^{18}
- 对于每个查询, 1 \leq x \leq 10^{18}.
- 对于第二类型的每个查询,给定 那时 x 位于 S 。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
查询处理过程如下:
- 在第一个查询中, 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.
示例输入 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
8 0 1 1 1 2 2 1 1 1 1 2 1 1 1 2 2 1
示例输出 3
1 1