#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。