#P9172. Pandaemonium Asphodelos: The First Circle (Savage)

    ID: 5254 传统题 4000ms 512MiB 尝试: 4 已通过: 3 难度: 8 上传者: 标签>CF2400提高+/省选-有序映射动态开点线段树不变量分析势能分析树的直径2022

Pandaemonium Asphodelos: The First Circle (Savage)

Problem 1001. Pandaemonium Asphodelos: The First Circle (Savage)

题目描述

糟糕,万魔殿出了些问题。阿谢姆的朋友 Themis 正等着你一起去看看。

然而,慌乱的万魔殿守卫 Erichthonios 把你们误认为敌人,开始攻击你们。你能保护自己和 Themis,直到他冷静下来吗?

为简化问题,Themis 的防御系统由排成一行的 nn 个方块组成。所有方块的初始权值均为 00,且具有相同的属性。Erichthonios 将进行 qq 次攻击,每次为以下四种之一:

  • 1 x c:Erichthonios 用锁链连接第 xx 个方块及距离它最近的 2c2c 个方块,赋予它们一种新属性,覆盖这些方块原有的属性,权值保持不变。若一侧不足 cc 个,就从另一侧补足,始终选中连续的 2c+12c+1 个方块。
  • 2 x y:将第 xx 个方块的属性复制给包含第 yy 个方块的、属性相同的最长连续段中的所有方块。该段左侧相邻方块的属性不同或已越界,右侧亦然。改变属性不会改变这些方块的权值。
  • 3 x v:将所有与第 xx 个方块属性相同的方块的权值增加 vv。
  • 4 x:Erichthonios 攻击防御系统。只有输出第 xx 个方块的权值,你才能抵御这次攻击。

注意:由于你不知道 Erichthonios 接下来会做什么,询问经过了编码,详见输入格式。

如果你不能解决这个问题,之后就会被 Hythlodaeus 嘲笑。你不想这样,对吧?

输入格式

输入包含多组测试数据。第一行包含测试数据组数 TT,其中 1≤T≤201\le T\le 20。

每组测试数据的第一行包含两个整数 nn 和 qq(3≤n≤1083\le n\le 10^8,1≤q≤1051\le q\le 10^5),分别表示防御系统的方块数和 Erichthonios 的攻击次数。

接下来 qq 行描述攻击。初始时,last=0last=0。

  • 1 x' c':包含三个整数,其中 1≤x′≤n1\le x'\le n,1≤c′≤⌊n−12⌋1\le c'\le \left\lfloor\frac{n-1}{2}\right\rfloor。实际参数为x=((x′−1)⊕last) mod n+1,x=((x'-1)\oplus last)\bmod n+1, $$c=((c'-1)\oplus last)\bmod\left\lfloor\frac{n-1}{2}\right\rfloor+1.$$
  • 2 x' y':包含三个整数,其中 1≤x′≤n1\le x'\le n,1≤y′≤n1\le y'\le n。实际参数为x=((x′−1)⊕last) mod n+1,x=((x'-1)\oplus last)\bmod n+1, y=((y′−1)⊕last) mod n+1.y=((y'-1)\oplus last)\bmod n+1.
  • 3 x' v:包含三个整数,其中 1≤x′≤n1\le x'\le n,1≤v≤1091\le v\le 10^9。实际参数为x=((x′−1)⊕last) mod n+1.x=((x'-1)\oplus last)\bmod n+1. vv 不进行编码。
  • 4 x':包含两个整数,其中 1≤x′≤n1\le x'\le n。实际参数为x=((x′−1)⊕last) mod n+1.x=((x'-1)\oplus last)\bmod n+1. 得到答案 AnswerAnswer 后,更新last=Answer&1073741823.last=Answer\mathbin{\&}1073741823.

其中,⊕\oplus 表示按位异或运算,&\& 表示按位与运算。

保证所有测试数据的 nn 之和不超过 2⋅1092\cdot 10^9,qq 之和不超过 10610^6。

输出格式

对于每组测试数据,每遇到一次第 44 类攻击,输出一行一个整数,表示所询问方块的权值。

样例

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 场(福州大学)。

原 PDF 题面