P16524 余生的第一天

#47 已经修复了，可以提交。并没有申请到重测，请自行重新提交此题。  >一次次不假思索地按下快门。\ >是为了抓住当时的快乐？\ >还是抓住当时的自己？

有一个 $n$ 个元素的序列 $s$。 有 $q$ 次操作，每次操作为以下两种之一： 1. 询问。给出 $l$、$r$、$V$，查询： $$\max^r_{i=l-1} \left (\sum^i_{\substack{k=l \\ |s_k| \le V}}s_k + \sum^r_{\substack{k=i+1 \\ |s_k| > V}}s_k \right)$$ 2. 单点修改。给出 $w$ 和 $k$，将 $s_w$ 设为 $k$。

本题**强制在线**，对于每次操作的 $l$、$r$ 或 $w$，记上一次查询的答案为 $last$。初始 $last=0$。 则解密为： - $l \gets (l \otimes |last|) \mod n +1$ - $r \gets (r \otimes |last|) \mod n +1$ - $w \gets (w \otimes |last|) \mod n +1$ 其中 $\otimes$ 是按位异或运算，若 $l>r$ 请交换 $l$ 和 $r$。 第一行两个整数 $n$ 和 $q$。 第二行 $n$ 个整数表示 $s_i$。 接下来 $q$ 行，每行 ```1 l r V``` 或 ```2 w k```，表示一种操作。

对于每个询问，一行一个整数表示答案。

### 数据范围 以下设 $G$ 表示测试点内所有 $\lvert s_i \rvert,\lvert V \rvert,\lvert k \rvert$ 的最大值。 对于 $100\%$ 的数据，保证：$1 \le n \le 5 \times 10^4$，$1 \le l,r \le n$，$1 \le w \le n$，$\lvert s_i \rvert,\lvert V \rvert,\lvert k \rvert \le 10^8$，$V \ge 0$。 | Subtask |分值 | $n \le$ | $q \le$ | $G \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $5$ | $5$ | $10$ | $10$ |无| | $2$ | $5$ | $200$ | < | $10^3$ |^| | $3$ | $10$ | $10^3$ | < | $10^5$ |^| | $4$ | $15$ | $5 \times 10^3$ | < | ^ | ^| | $5$ |$15$ | $5 \times 10^4$ | < | $10^8$ |A | | $6$ |$10$ | ^ | ^ | ^ | B | | $7$ |$40$ | ^ | ^ | ^ | 无 | 特殊性质 A：没有修改操作。 特殊性质 B：$s_i\ge 0$。