#P9172. Pandaemonium Asphodelos: The First Circle (Savage)
Pandaemonium Asphodelos: The First Circle (Savage)
Problem 1001. Pandaemonium Asphodelos: The First Circle (Savage)
题目描述
糟糕,万魔殿出了些问题。阿谢姆的朋友 Themis 正等着你一起去看看。
然而,慌乱的万魔殿守卫 Erichthonios 把你们误认为敌人,开始攻击你们。你能保护自己和 Themis,直到他冷静下来吗?
为简化问题,Themis 的防御系统由排成一行的 个方块组成。所有方块的初始权值均为 ,且具有相同的属性。Erichthonios 将进行 次攻击,每次为以下四种之一:
1 x c:Erichthonios 用锁链连接第 个方块及距离它最近的 个方块,赋予它们一种新属性,覆盖这些方块原有的属性,权值保持不变。若一侧不足 个,就从另一侧补足,始终选中连续的 个方块。2 x y:将第 个方块的属性复制给包含第 个方块的、属性相同的最长连续段中的所有方块。该段左侧相邻方块的属性不同或已越界,右侧亦然。改变属性不会改变这些方块的权值。3 x v:将所有与第 个方块属性相同的方块的权值增加 。4 x:Erichthonios 攻击防御系统。只有输出第 个方块的权值,你才能抵御这次攻击。
注意:由于你不知道 Erichthonios 接下来会做什么,询问经过了编码,详见输入格式。
如果你不能解决这个问题,之后就会被 Hythlodaeus 嘲笑。你不想这样,对吧?
输入格式
输入包含多组测试数据。第一行包含测试数据组数 ,其中 。
每组测试数据的第一行包含两个整数 和 (,),分别表示防御系统的方块数和 Erichthonios 的攻击次数。
接下来 行描述攻击。初始时,。
1 x' c':包含三个整数,其中 ,。实际参数为 $$c=((c'-1)\oplus last)\bmod\left\lfloor\frac{n-1}{2}\right\rfloor+1.$$2 x' y':包含三个整数,其中 ,。实际参数为3 x' v:包含三个整数,其中 ,。实际参数为 不进行编码。4 x':包含两个整数,其中 。实际参数为 得到答案 后,更新
其中, 表示按位异或运算, 表示按位与运算。
保证所有测试数据的 之和不超过 , 之和不超过 。
输出格式
对于每组测试数据,每遇到一次第 类攻击,输出一行一个整数,表示所询问方块的权值。
样例
1
16 12
3 10 16
4 2
1 1 6
1 5 6
1 9 7
1 15 7
2 2 10
2 2 13
3 1 16
4 16
4 9
4 4
16
32
32
16
提示
样例中解码后的攻击如下:
3, x = 10, v = 16
4, x = 2
1, x = 1, c = 1
1, x = 5, c = 1
1, x = 9, c = 2
1, x = 15, c = 2
2, x = 2, y = 10
2, x = 2, y = 13
3, x = 1, v = 16
4, x = 16
4, x = 9
4, x = 4
来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。