可持久化队列

题目描述:

这是一道假的模板题

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

• 1 ver t 表示将 A[ver] 复制到 A[i]，并在 A[ver] 结尾插入元素 t
• 2 ver 表示将 A[ver] 复制到 A[i]，并删除 A[ver] 开头的元素。

此外，你需要维护一个变量 hash，其初始值为 0，每次执行完第二类操作时，将 hash 变为 (31×hash+x)mod2³²，其中 x 是被删除的元素。

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

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

输入格式:

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

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

输出格式:

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

样例输入:

样例1：
9 0
1 0 1
1 1 2
2 1
2 2
2 2
2 4
1 4 5
2 7
2 8

样例2：
9 1
1 0 1
1 1 2
2 1
2 3
2 34
2 997
1 30789 30788
2 30790
2 954345

样例输出:

样例1：
29584452

样例2：
29584452

提示:

样例1解释：

iiii	A[i]ii	第 i 次操作删除的数（若有）
0	[]
1	[1]
2	[1,2]
3	[]	1
4	[2]	1
5	[2]	1
6	[]	2
7	[2,5]
8	[5]	2
9	[]	5

 

样例2解释：

解密后，与样例一相同

测试点编号iii	Tiiiiii	tyiii
1	103​​	1
2, 3, 4	105	1
5, 6	106	0
7, 8, 9, 10	106​​	1

对于所有操作，ver≥0，ver 小于当前操作编号。

对于第一类操作，0≤t<100,000,000

请使用无符号整数进行输入输出！变量应使用 unsigned 类型，printf 和 scanf 应使用 %u 格式。

如果你使用冲击满分的算法，但是使用 scanf，你的程序很可能将花费超过 80% 的运行时间在输入数据。所以请务必使用读入优化！

时间限制: 1000ms
空间限制: 128MB

---