← 返回题目列表

Codeforces · 707/D

D. 持久书柜

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

最近在学校 Alina 学习了什么是持久数据结构:它们是始终保留自身先前版本并在修改时访问它的数据结构。

回到家后,Alina 决定发明她自己的持久数据结构。发明并没有花很长时间:她的床后面就有一个书柜。 Alina 认为书柜是持久数据结构的不错选择。最初书柜是空的,因此任何架子的任何位置都没有书。

书柜由 n 个架子组成,每个架子上正好有 m 个位置可以放书。 Alina 通过从 1 到 n 的整数以及从 1 到 m 的货架位置来枚举货架。最初书柜是空的,因此书柜中任何架子的任何位置都没有书。

Alina 写下 q 操作,这些操作将连续应用于书柜。每个操作都有以下四种类型之一:

- 1 i j — 如果书架 i 上没有书,则将书放在位置 j 处。
- 2 i j — 如果书架 i 上有书,则将书从位置 j 移走。
- 3 i — 反转书籍放置在书架 i 上。这意味着,应该从书架 i 上每个有书的位置移除书,并且应该在书架 i 上没有书的每个位置放置一本书。
- 4 k — 将书柜中的书籍返回到应用第 k 次操作后的状态。特别地,k = 0意味着书柜应处于初始状态,因此书柜中的每一本书都应从其位置移走。

应用每个操作后,Alina 对书柜中的书籍数量感兴趣。阿丽娜在学校获得了“A”,并且毫无问题地找到了这个价值观。你会这样做吗?

输入

输入的第一行包含三个整数 n、m 和 q (1 ≤ n, m ≤ 103, 1 ≤ q ≤ 105)——分别是书柜尺寸和操作次数。

接下来的 q 行按时间顺序描述操作 - 其中第 i 行以语句中描述的四种格式之一描述第 i 个操作。

保证货架索引和位置索引是正确的,并且在每种第四类操作中,数字k对应于其之前的某个操作或等于0。

输出

对于每个操作,在单独的行中应用后打印书柜中的书籍数量。答案应按时间顺序打印。

示例

输入 #1

2 3 3
1 1 1
3 2
4 0

输出 #1

1
4
0

输入 #2

4 2 6
3 2
2 2 2
3 3
3 2
2 2 2
3 2

输出 #2

2
1
3
3
2
4

输入 #3

2 2 2
3 2
2 2 1

输出 #3

2
1

注意

此图展示了第二个示例案例。