← 返回题目列表

AtCoder · abc356_f

I. 距离元件尺寸查询

中文机器翻译题面 查看原题

分数: 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