#STL011. 稀疏棋盘

稀疏棋盘

稀疏棋盘

棋盘可以用任意整数行坐标 r、列坐标 c 表示位置,但只保存被明确写入的位置。初始没有保存任何位置。每个位置可保存一个整数值,你需要执行写入、查询、删除和计数。

支持以下指令:

指令 行为 输出
SET r c v 在坐标 (r,c) 保存 v;已经保存时覆盖 无
GET r c 查询坐标 (r,c) 已保存时输出值,否则输出 EMPTY
ERASE r c 删除坐标 (r,c) 的记录 删除成功输出 1,否则输出 0
COUNT 查询保存的不同坐标数 输出数量

两个坐标只有行、列均相同才是同一个位置;(r,c) 与 (c,r) 不一定相同。0 是可以保存的普通值,SET r c 0 不会删除记录。查询一个未保存的位置不改变棋盘。空棋盘的保存数量为 0。

输入格式

第一行整数 q。接下来 q 行,每行一条上述指令。

输出格式

按指令顺序,对每次 GET、ERASE、COUNT 输出一行。SET 不输出;若没有需输出的指令,输出为空。

数据范围

  • 1 ≤ q ≤ 200000。
  • −10⁹ ≤ r、c、v ≤ 10⁹。
  • 输入保证指令格式合法。

样例 1

输入:

12
GET 0 0
SET 0 0 0
COUNT
GET 0 0
SET 0 0 -7
SET -1 2 9
COUNT
ERASE 0 0
GET 0 0
ERASE 0 0
GET -1 2
COUNT

输出:

EMPTY
1
0
2
1
EMPTY
0
9
1

解释:写入 (0,0) 的值 0 后,它成为一个已保存的坐标,COUNT 输出 1,GET 输出 0。覆盖成 −7 不增加坐标数。删除它后,该坐标的查询输出 EMPTY,而 (−1,2) 仍保存 9。

样例 2

输入:

7
SET 1 2 5
SET 2 1 0
GET 1 2
GET 2 1
ERASE 2 1
COUNT
GET 2 1

输出:

5
0
1
1
EMPTY

解释:(1,2) 和 (2,1) 是不同位置。后者保存的值虽然为 0,仍可以被查询、计数和成功删除。删除后再次查询才输出 EMPTY。