CF2255E1 What Will Remain at the End? (Easy Version)

这是本题的简单版本。两个版本的唯一区别在于初始数组和操作 $1$ 中 $x$ 允许的取值范围。在本版本中，所有这些值都属于 $\{-1,0,1\}$。 你只能在两个版本都通过时对本题进行 Hack。 在最终出击之前，Chtholly 向 Willem 提出了三个问题。 第二个问题是：如果天空真的迎来终结，还会剩下什么？ Willem 无法直接回答她，而是翻开一本包含 $n$ 条记录的编年史，记录编号从 $1$ 到 $n$。每条记录包含一个整数：正值表示希望，负值表示绝望。 编年史的初始内容构成了一个数组 $a_1,a_2,\ldots,a_n$，称为 $0$ 号版本。Chtholly 接下来进行 $q$ 次操作。对于每个 $1\le i\le q$，第 $i$ 次操作由第 $i-1$ 号版本产生新的 $i$ 号版本。 每次操作有以下四种类型之一： - $\texttt{1 l r x}$：将所有 $l\le k\le r$ 的 $a_k$ 赋值为 $x$。 - $\texttt{2 l r}$：将所有 $l\le k\le r$ 的 $a_k$ 取反，即 $a_k\gets -a_k$。 - $\texttt{3 l r}$：将所有 $l\le k\le r$ 的 $a_k$ 变为 $\max(a_k,0)$。 - $\texttt{4 p}$：对于之前所有版本 $0,1,\ldots, i-1$，考虑每个版本中第 $p$ 个位置的数值，设这些值为 $b_0,b_1,\ldots,b_{i-1}$。求这个序列所有非空连续子段的最大和。 如果是 $1$、$2$ 或 $3$ 型操作，则在第 $i-1$ 号版本的基础上进行相应区间修改，得到第 $i$ 号版本。$4$ 型操作不会修改数组，因此 $i$ 号版本与 $i-1$ 号版本相同。 所有操作均经过编码，且必须按顺序处理。它们的解码依赖于 $\mathrm{lastans}$，该值在每次 $4$ 型操作后更新。 请帮助 Willem 回答所有类型为 $4$ 的操作。 $^\ast$ 一个数组 $c$ 是数组 $b$ 的连续子段，如果 $c$ 能通过从 $b$ 的开头和结尾各删除若干（可以为零或所有）元素得到。

每组测试包含若干测试用例。第一行包含测试用例数 $t$（$1\le t \le 10^4$）。每组测试的数据描述如下。 每个测试用例第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le5\cdot10^5$）——数组长度和操作数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$a_i\in\{-1,0,1\}$）——$0$ 号版本的数组。 接下来的 $q$ 行，每行描述一次操作，编码格式如下：行第一个数字为操作类型。 - $\texttt{1 u v x}$ ($0\le u,v < 2^{64}$，$x\in\{-1,0,1\}$) - $\texttt{2 u v}$ ($0\le u,v < 2^{64}$) - $\texttt{3 u v}$ ($0\le u,v < 2^{64}$) - $\texttt{4 u}$ ($0\le u < 2^{64}$) 每个操作都经过编码并需按顺序处理，解码依赖于 $\mathrm{lastans}$。 初始时 $\mathrm{lastans}=0$。每当回答完 $4$ 型操作后，将 $\mathrm{lastans}$ 设为该答案对 $2^{64}$ 取模后的最小非负剩余，其余类型操作不影响 $\mathrm{lastans}$。 对于每个被编码坐标 $y$，定义 $d(y)=((y\oplus \mathrm{lastans}) \bmod n)+1$，其中 $\oplus$ 表示按位异或运算。 - 对于 $\texttt{1 u v x}$ 操作，$l=\min(d(u),d(v))$，$r=\max(d(u),d(v))$，$x$ 不加编码。 - 对于 $\texttt{2 u v}$ 或 $\texttt{3 u v}$ 操作，$l=\min(d(u),d(v))$，$r=\max(d(u),d(v))$。 - 对于 $\texttt{4 u}$ 操作，$p=d(u)$。 操作类型不经过编码。每次 $4$ 型操作后记得更新 $\mathrm{lastans}$。 保证所有测试用例中 $n$ 的总和不超过 $5\cdot10^5$。 保证所有测试用例中 $q$ 的总和不超过 $5\cdot10^5$。

对于每个 $4$ 型操作，输出一个整数，表示所有版本中第 $p$ 位的数值所形成序列的非空连续子段最大和。

在第一个测试用例中，第一次操作时 $\mathrm{lastans}=0$，因此编码坐标 $1$ 被解码为第 $2$ 个位置。此时只考虑 $0$ 号版本，该位置值为 $-1$，答案为 $-1$。 此后 $\mathrm{lastans}=2^{64}-1=18\,446\,744\,073\,709\,551\,615$。因此编码区间 $[18\,446\,744\,073\,709\,551\,615,18\,446\,744\,073\,709\,551\,613]$ 被解码为 $[1,3]$，编码坐标 $18\,446\,744\,073\,709\,551\,614$ 被解码为第 $2$ 个位置。 第二次询问前，第 $2$ 位置在 $0,1,2$ 号版本的值为 $-1$、$-1$、$1$，最大连续子段和为 $1$。 第三次询问前，第 $2$ 位在 $0,1,\ldots,5$ 号版本的值为 $[-1,-1,1,1,1,-1]$，其中连续 $3$ 个 $1$ 形成的子段和为 $3$。 注意第一次、第二次和第三次询问分别生成了第 $1$、第 $3$ 和第 $6$ 号版本，即使这些操作没有更改数组内容。 在第二个测试用例中，第一次询问的是第 $1$ 个位置，答案为 $1$。之后 $\mathrm{lastans}=1$，编码操作 $\texttt{1 0 3 -1}$ 解码为 $\texttt{1 2 3 -1}$。 第二次询问前，第 $3$ 个位置在 $0,1,2$ 号版本的值为 $1,1,-1$，答案为 $2$。 之后 $\mathrm{lastans}=2$。编码操作 $\texttt{2 2 3}$ 和 $\texttt{3 3 0}$ 分别解码为 $\texttt{2 1 2}$ 和 $\texttt{3 2 3}$。最后一次询问前，第 $2$ 个位置在 $0,1,\ldots,5$ 号版本的值为 $[-1,-1,-1,-1,1,1]$，最大连续子段和为 $2$。 由 ChatGPT 5 翻译