带删除标记的哈希集合

题目描述

请使用长度为 m 的开放地址哈希表维护一个整数集合。哈希函数为：

h(x)=((x mod m)+m) mod m

发生冲突时使用线性探测。哈希表中的桶有三种状态：

• EMPTY：从未使用；
• USED：当前保存一个关键字；
• DELETED：关键字已经删除，但探测链不能在这里停止。

需要处理 q 个操作：

• 1 x：插入 x。若已经存在则不重复插入；若表已满则忽略本次插入；
• 2 x：查询 x 是否存在，输出 Yes 或 No；
• 3 x：删除 x。若不存在则不进行任何操作。

输入格式

第一行两个整数 m、q。

接下来 q 行，每行两个整数 op、x。

输出格式

对于每个查询操作 2 x，输出一行 Yes 或 No。

7 8
1 10
1 17
1 24
3 17
2 24
2 17
1 31
2 31

Yes
No
Yes

数据范围

• 1 <= m <= 200003
• 1 <= q <= 200000
• -10^9 <= x <= 10^9