#STL017. 邻近坐标

邻近坐标

邻近坐标

导航面板保存一些一维整数坐标,初始没有坐标。你可以插入或删除坐标,也可以查询某个位置附近最近的现存坐标。相同距离时,面板固定选择较小的坐标。

依次处理所有操作。

输入格式

第一行一个整数 q。接下来 q 行,每行是以下一种操作:

  • INSERT x:插入坐标 x,已经存在则忽略,不输出。
  • ERASE x:删除坐标 x,存在且删除成功输出 1,否则输出 0。
  • NEAR x:输出与 x 距离最近的现存坐标;相同距离取较小者。集合为空时输出 EMPTY。

输出格式

按照操作顺序,每个 ERASE 或 NEAR 的结果独占一行。只有 INSERT 操作时,可以没有输出。

数据范围与约定

  • 1≤q≤200000。
  • 所有 x 在 [−1000000000,1000000000] 中。
  • 集合只保存不同坐标。距离定义为绝对值 |坐标−x|。

样例 1

输入:

10
NEAR 0
INSERT 5
INSERT -5
NEAR 0
INSERT 5
ERASE 8
ERASE -5
NEAR 0
ERASE 5
NEAR 1

输出:

EMPTY
-5
0
1
5
1
EMPTY

说明:首次查询时为空。插入 5 与 −5 后,0 到二者距离相同,选 −5。重复插入 5 不增加元素;删除不存在的 8 返回 0。最后两个坐标都被删除,查询再次返回 EMPTY。

样例 2

输入:

7
INSERT 1
INSERT 3
NEAR 2
NEAR 4
ERASE 1
NEAR 0
ERASE 1

输出:

1
3
1
3
0

说明:2 到 1 和 3 距离相同,选 1;4 最近的是 3。删除 1 后,0 只能返回 3;再次删除 1 返回 0。

原创说明

本题的场景、题面、样例、实现与数据由本题单作者独立编写;仅使用公开的算法概念与 C++ 标准库接口,未使用第三方题面或测试文件。