← 返回题目列表

Codeforces · 1701/F

F. 积分

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

如果 $$$i < j < k$$$ 且 $$$k - i \le d$$$,则坐标线上的三重点 $$$i$$$、$$$j$$$ 和 $$$k$$$ 被称为美丽的。

给你坐标线上的一组点,最初是空的。您必须处理三种类型的查询:

- 添加一个点;
- 删除一个点;
- 计算由属于该集合的点组成的美丽三元组的数量。

输入

第一行包含两个整数 $$$q$$$ 和 $$$d$$$ ($$$1 \le q, d \le 2 \cdot 10^5$$$) — 分别是查询次数和定义三元组是否美丽的参数。

第二行包含 $$$q$$$ 整数 $$$a_1, a_2, \dots, a_q$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) 表示查询。整数 $$$a_i$$$ 表示第 $$$i$$$ 个查询,如下所示:

- 如果点 $$$a_i$$$ 属于集合,则将其删除;否则,添加;
- 添加或删除点后,打印漂亮三元组的数量。

输出

对于每个查询,打印一个整数——处理相应查询后美丽三元组的数量。

示例

输入 #1

7 5
8 5 3 2 1 5 6

输出 #1

0
0
1
2
5
1
5