P17286 "IXOI R2" Horizon Blue

 (The picture is from the Phigros song artwork. Please contact to remove if infringement.)

You are given a sequence $a$ of length $n$, and $m$ operations. You must process the following two types of operations in a forced online manner. - `1 x y`: increase the $x$-th number in the sequence by $y$. - `2 l r`: compute the sum of the maximum values of all non-empty contiguous subsegments within the interval $[l,r]$, and output the result modulo $2^{32}$. It is guaranteed that all numbers in the sequence are pairwise distinct at any time.

The first line contains two integers $n,m$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the initial sequence. The next $m$ lines each follow one of the two formats: - `1 x y`. - `2 l r`. Let `last` be the actual output of the previous query. Initially, `last = 0`. All XOR operations are performed on unsigned 32-bit integers. - For an input operation `1 x y`, the actual modified position is $$ x_{\mathrm{real}}=x\oplus \mathrm{last}. $$ The parameter $y$ is not XORed. - For an input operation `2 l r`, the actual queried interval is $$ [l_{\mathrm{real}},r_{\mathrm{real}}] =[l\oplus \mathrm{last},\ r\oplus \mathrm{last}]. $$ - Let the true answer of this query be $S$. Output $$ \mathrm{ans}=S\bmod 2^{32}, $$ and set $$ \mathrm{last}\leftarrow \mathrm{ans}. $$ It is guaranteed that all operations are valid after decoding.

For each operation of type 2, output one integer per line, representing the answer modulo $2^{32}$.

**This problem uses bundled testdata.** | Subtask | $n,m\le$ | Special Property | Score | | :-----: | :-----------------: | :--------------: | :---: | | $1$ | $10^4$ | None | $10$ | | $2$ | $2\times10^5$ | Yes | $30$ | | $3$ | $10^5$ | None | $20$ | | $4$ | $1.5\times10^5$ | None | $20$ | | $5$ | $2\times10^5$ | None | $20$ | Special Property: after decoding, all queries satisfy $l=1,r=n$. For all data, it is guaranteed that: $$ 0\le a_i,y\le 10^9, 1\le x_{\mathrm{real}},l_{\mathrm{real}}\le r_{\mathrm{real}}\le n $$ and the encoded $x,l,r$ in the input are in $[0,2^{32}-1]$. It is guaranteed that at any time $a_i\le 2\times 10^9$, and all numbers in the sequence are pairwise distinct. Translated by ChatGPT 5