#6203. 可持久化队列

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: dram

题目描述


这是一道假的模板题

我们有一个数组 A ,初始时只有 A[0] 是空序列。对于第 i 个操作:

  • 1 ver t 表示将 A[ver] 复制 A[i] ,并在 A[ver] 结尾插入元素 t
  • 2 ver 表示将 A[ver] 复制 A[i] ,并删除 A[ver] 开头的元素(保证 A[i] 非空)

此外,你需要维护一个变量 hash ,其初始值为 0 ,每次执行完第二类操作时,将 hash 变为 (31 \times hash + x) \bmod 2^{32} ,其中 x 是被删除的元素。

hash 是你的最终输出的答案。

此外,输入数据有可能加密,取决于输入参数 ty 的值。如果 ty = 0 ,那么数据没有加密;否则, ty=1 ,那么读入 ver t 的值,其真实值应与当前的 hash 取按位异或,也就是说真实值应为 ver \oplus hash 和(对于第一类操作) t \oplus hash

输入格式

第一行有两个整数, T ty ,表示有多少个操作,和数据是否加密。

之后的 T 行,每一行表示一个如上所述的操作。

输出格式

只有一行,表示执行完所有操作之后, hash 的值。

样例

样例输入一

9 0
1 0 1
1 1 2
2 1
2 2
2 2
2 4
1 4 5
2 7
2 8

样例输出一

29584452

样例解释一

i A[i] i 次操作删除的数(若有)
0 []
1 [1]
2 [1,2]
3 [] 1
4 [2]
5
6 [] 2
7 [2,5]
8 [5] 2
9 [] 5

样例输入二

9 1
1 0 1
1 1 2
2 1
2 3
2 34
2 997
1 30789 30788
2 30790
2 954345

样例输入二

29584452

样例解释二

解密后,与样例一相同

数据范围与提示

测试点编号 T ty
1 10^3 1
2, 3, 4 10^5
5, 6 10^6 0
7, 8, 9, 10 1

对于所有操作,保证操作合法,即格式正确,不会在空的版本上进行操作 2 ver \geq 0 ver 小于当前操作编号。

对于第一类操作, 0 \leq t \lt 10000000


请使用无符号整数进行输入输出!变量应使用 unsigned 类型,printfscanf 应使用 %u 格式。

如果你使用冲击满分的算法,但是使用 scanf,你的程序很可能将花费超过 80\% 的运行时间在输入数据。所以请务必使用读入优化!可以参考附加文件中 bqsg 提供的 read.cpp 实现的 A + B Problem 的程序。