103565: [Atcoder]ABC356 F - Distance Component Size Query
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $525$ points
Problem Statement
You are given an integer $K$. For a set $S$ that is initially empty, process $Q$ queries of the following two types in order:
1 x: An integer $x$ is given. If $x$ is in $S$, remove $x$ from $S$. Otherwise, add $x$ to $S$.2 x: An integer $x$ that is in $S$ is given. Consider a graph where the vertices are the numbers in $S$, and there is an edge between two numbers if and only if the absolute difference between them is at most $K$. Print the count of vertices in the connected component that contains $x$.
Constraints
- $1 \leq Q \leq 2\times 10^5$
- $0 \leq K \leq 10^{18}$
- For each query, $1 \leq x \leq 10^{18}$.
- For each query of the second type, the given $x$ is in $S$ at that point.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$Q$ $K$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$
Each query is given in the following format:
$1$ $x$
$2$ $x$
Output
Process the queries.
Sample Input 1
7 5 1 3 1 10 2 3 1 7 2 3 1 10 2 3
Sample Output 1
1 3 2
The query processing proceeds as follows:
- In the first query, $3$ is added to $S$, resulting in $S=\{3\}$.
- In the second query, $10$ is added to $S$, resulting in $S=\{3,10\}$.
- In the third query, consider a graph with vertices $3$ and $10$ and no edges. The connected component containing $3$ has a size of $1$, so print $1$.
- In the fourth query, $7$ is added to $S$, resulting in $S=\{3,7,10\}$.
- In the fifth query, consider a graph with vertices $3$, $7$, and $10$, with edges between $3$ and $7$, and $7$ and $10$. The connected component containing $3$ has a size of $3$, so print $3$.
- In the sixth query, $10$ is removed from $S$, resulting in $S=\{3,7\}$.
- In the seventh query, consider a graph with vertices $3$ and $7$, with an edge between them. The connected component containing $3$ has a size of $2$, so print $2$.
Sample Input 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
Sample Output 2
10
Sample Input 3
8 0 1 1 1 2 2 1 1 1 1 2 1 1 1 2 2 1
Sample Output 3
1 1
Output
得分：525分
---
### 问题描述
给定一个整数 $K$。初始为空的集合 $S$ 需要处理 $Q$ 个以下两种类型的查询，顺序进行：
1. `1 x`：给定一个整数 $x$。如果 $x$ 在 $S$ 中，从 $S$ 中移除 $x$。否则，将 $x$ 添加到 $S$。
2. `2 x`：给定在 $S$ 中的整数 $x$。考虑一个图，其中顶点是集合 $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$
$query_1$
$\vdots$
$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
```