← 返回题目列表

Codeforces · 178/C1

C1. 智能海狸和解决碰撞

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

ABBYY 的智能海狸有很多爱好。其中之一是构建高效的哈希表。哈希表中最严重的问题之一是解决冲突。海狸对这个问题非常感兴趣,他决定详细探究一下。

我们假设哈希表由编号为 0 到 h - 1 的 h 个单元组成。向其中添加或删除对象。每个对象都有自己唯一的标识符。此外,每个对象都有一个相应的哈希值 - 0 到 h - 1 之间的整数(含)。当一个对象被添加到表中时,如果该对象的哈希值对应的单元格是空闲的,那么这个对象就到那里。如果单元格已被另一个对象占据,则会发生碰撞。当从表中删除对象时,它所占用的单元格变为空。

智能海狸最近了解了线性探测来解决碰撞的方法。如下。假设添加的对象的哈希值等于 t 并且表的单元格 t 已被占用。然后我们尝试将此对象添加到单元格 (t + m) mod h 中。如果它也被占用,那么我们尝试 cell (t + 2·m) mod h,然后 cell (t + 3·m) mod h,依此类推。请注意,在某些情况下,新对象可能无法添加到表中。保证该问题的输入不包含此类情况。

运算 a mod b 表示我们取数字 a 除以数字 b 的余数。

对于海狸来说,这种技术立即显得非常不理想,他决定评估其低效率。因此,您将获得一系列操作,每个操作要么向表中添加一个对象,要么从表中删除一个对象。添加新对象时,将执行对表的一系列调用。对占用单元的调用称为虚拟单元。换句话说,如果上述算法的结果是对象被添加到单元 (t + i·m) mod h (i ≥ 0),则恰好执行了 i 次虚拟调用。

您的任务是计算给定的添加和删除序列对表的虚拟调用总数。当从表中删除对象时,假设没有执行任何虚拟调用。在执行操作之前该表是空的,也就是说,最初它不包含任何对象。

输入

输入的第一行包含三个整数 h、m 和 n (1 ≤ m < h),以空格分隔,其中 h 是哈希表的大小,m 是用于解决冲突的数字,n 是操作的数量。

接下来的 n 行包含操作的描述。它们的执行顺序与它们在输入文件中出现的顺序相对应。每个操作都由一行描述。操作说明如下:

- “+ id hash”这是向表中添加对象的操作格式。第一个字符是“+”(ASCII 43),后跟一个空格,然后是对象标识符 id (0 ≤ id ≤ 109),然后是另一个空格,以及给定对象哈希的哈希值 (0 ≤ hash < h)。该对象的对象标识符和哈希值都是整数。
- "-id"这是从表中删除对象的操作格式。第一个字符是“-”(ASCII 45),后跟一个空格,然后是对象标识符 id (0 ≤ id ≤ 109)。对象标识符是一个整数。

保证对于所有加法运算,id 的值是唯一的。它还保证了初始数据是正确的,即总是可以向哈希表添加对象,并且不会删除不存在的对象。

获得 20 点的输入限制为:

- 1 ≤ h ≤ 5000
- 1 ≤ n ≤ 5000

获得 50 点的输入限制为:

- 1 ≤ h ≤ 5·104
- 1 ≤ n ≤ 5·104

获得 100 点的输入限制为:

- 1 ≤ h ≤ 2·105
- 1 ≤ n ≤ 2·105

输出

打印单个数字 — 对哈希表的虚拟调用总数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流和 %I64d 说明符。

示例

输入 #1

10 2 7
+ 11 0
+ 22 2
+ 33 6
+ 44 0
+ 55 0
- 22
+ 66 0

输出 #1

7

输入 #2

5 1 6
+ 123 0
+ 234 1
+ 345 2
- 234
+ 456 0
+ 567 0

输出 #2

4