CF2255E2 What Will Remain at the End? (Hard Version)

这是该问题的 Hard 版本。两个版本唯一的区别在于初始数组和操作 $1$ 中 $x$ 的取值范围。在本版本中，这些值可以是 $[-10^9, 10^9]$ 区间内的任意整数。如果你要 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$ 更新为 $a_k\gets\max(a_k,0)$。 - $\texttt{4 p}$：对于所有先前的版本 $0,1,\ldots,i-1$，取下标 $p$ 处的值，形成序列 $b_0,b_1,\ldots,b_{i-1}$。求该序列所有非空子段的最大和 $^\ast$。 如果是 $1,2,3$ 操作，则将版本 $i-1$ 上指定区间修改得到新版本 $i$。类型 $4$ 操作不会修改数组，因此版本 $i$ 与 $i-1$ 相同。 操作经过编码，且必须按顺序处理。解码依赖于 $\mathrm{lastans}$，而该值会在每次 $4$ 操作后更新。 请帮助 Willem 回答每个 $4$ 类型的操作。 $^\ast$ 若有一个数组 $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$（$-10^9\le a_i\le 10^9$），即第 $0$ 版的数组。 接下来 $q$ 行描述 $q$ 次操作，每行按如下某种格式给出（均为编码后的数据）： - $\texttt{1 u v x}$（$0\le u,v < 2^{64}$，$-10^9\le x\le 10^9$）； - $\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$ 操作后，将答案对 $2^{64}$ 取模后的最小非负余数赋给 $\mathrm{lastans}$。其它类型操作不会影响 $\mathrm{lastans}$。 对于每个被编码的坐标 $y$，设 \[ d(y) = \left((y \oplus \mathrm{lastans}) \bmod n\right) + 1 \] 其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 - 若操作为 $\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$ 版，下标 $2$ 处的值为 $-3$，因此答案为 $-3$。 现在 $\mathrm{lastans}=2^{64}-3=18\,446\,744\,073\,709\,551\,613$。此时编码区间 $[18\,446\,744\,073\,709\,551\,613,18\,446\,744\,073\,709\,551\,615]$ 译码后为 $[1,3]$，编码坐标 $18\,446\,744\,073\,709\,551\,612$ 对应第 $2$ 个位置。 在第二次查询前，下标 $2$ 位置的所有历史版本（$0$、$1$、$2$）的值为 $-3$、$-3$、$3$，其最大子段和为 $3$。 在第三次查询前，下标 $2$ 处各历史版本 $0,1,\ldots,5$ 的值为 $[-3,-3,3,3,3,-4]$，连续三个 $3$ 构成的子段和为 $9$。 注意第一次、第二次、第三次查询时分别生成了 $1,3,6$ 号版本，尽管这些查询并未更改数组。 在第二个用例中，第一次查询询问位置 $1$，因此答案为 $1$。之后 $\mathrm{lastans}=1$，编码操作 $\texttt{1 0 3 -1}$ 解码后为 $\texttt{1 2 3 -1}$。 在第二次查询前，下标 $3$ 处历史版本（$0,1,2$）的值为 $3$、$3$、$-1$，最大子段和为 $6$。 随后 $\mathrm{lastans}=6$，编码操作 $\texttt{2 6 7}$ 和 $\texttt{3 7 4}$ 解码后分别变为 $\texttt{2 1 2}$ 和 $\texttt{3 2 3}$。在最后一次查询前，下标 $2$ 处历史版本 $0,1,\ldots,5$ 的值为 $[-2,-2,-1,-1,1,1]$，其最大非空子段和为 $2$。 由 ChatGPT 5 翻译