CF178C1 Smart Beaver and Resolving Collisions

ABBYY 的聪明海狸有很多爱好，其中之一就是构建高效的哈希表。哈希表中最严重的问题之一就是解决冲突。海狸对这个问题非常感兴趣，决定深入研究。 我们假设哈希表有 $h$ 个单元格，编号从 $0$ 到 $h-1$。对象可以被添加到哈希表中，也可以从中删除。每个对象都有唯一的标识符。此外，每个对象还有一个对应的哈希值——一个在 $0$ 到 $h-1$ 之间（包含端点）的整数。当一个对象被添加到哈希表时，如果该对象的哈希值对应的单元格是空的，那么该对象就放在那里。如果该单元格已经被其他对象占用，就发生了冲突。当一个对象从哈希表中删除时，它所占用的单元格变为空。 聪明的海狸最近学会了一种解决冲突的方法——线性探查法。方法如下：假设要添加的对象的哈希值为 $t$，而哈希表的第 $t$ 个单元格已经被占用。那么我们尝试将该对象添加到单元格 $(t+m) \bmod h$。如果这个单元格也被占用，则尝试单元格 $(t+2·m) \bmod h$，然后是 $(t+3·m) \bmod h$，以此类推。注意，在某些情况下，可能无法将新对象添加到哈希表中。保证本题输入数据不会出现这种情况。 操作 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。 这个方法立刻让海狸觉得效率很低，于是他决定评估其低效程度。给定一系列操作，每个操作要么是向哈希表中添加一个对象，要么是删除一个对象。当添加新对象时，会对哈希表进行一系列访问。访问被占用的单元格称为“虚访问”。换句话说，如果上述算法最终将对象添加到单元格 $(t+i·m) \bmod h$（$i \geq 0$），那么恰好进行了 $i$ 次虚访问。 你的任务是计算给定操作序列中虚访问的总次数。删除对象时不进行虚访问。哈希表在操作开始前为空，即最初不包含任何对象。

输入的第一行包含三个整数 $h$、$m$ 和 $n$（$1 \leq m < h$），用空格分隔，分别表示哈希表的大小、用于解决冲突的数和操作数。 接下来的 $n$ 行描述操作，按输入顺序执行。每个操作占一行，格式如下： - “+ id hash” 表示向哈希表中添加一个对象。第一个字符是 “+”，后跟一个空格，然后是对象标识符 $id$（$0 \leq id \leq 10^{9}$），再跟一个空格，最后是该对象的哈希值 $hash$（$0 \leq hash < h$）。对象标识符和哈希值均为整数。 - “- id” 表示从哈希表中删除一个对象。第一个字符是 “-”，后跟一个空格，然后是对象标识符 $id$（$0 \leq id \leq 10^{9}$）。对象标识符为整数。 保证所有添加操作的 $id$ 值唯一。保证输入数据合法，即总能将对象添加到哈希表中，也不会删除不存在的对象。 获得 20 分的输入范围： - $1 \leq h \leq 5000$ - $1 \leq n \leq 5000$ 获得 50 分的输入范围： - $1 \leq h \leq 5 \cdot 10^{4}$ - $1 \leq n \leq 5 \cdot 10^{4}$ 获得 100 分的输入范围： - $1 \leq h \leq 2 \cdot 10^{5}$ - $1 \leq n \leq 2 \cdot 10^{5}$

输出一个整数，表示哈希表所有操作中虚访问的总次数。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。推荐使用 cin、cout 流和 %I64d。

由 ChatGPT 4.1 翻译