Background

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

Problem Description

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.

Input Format

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.

Output Format

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

10 10
305 6197 2133 7051 30 8411 2622 2173 8522 2998
1 2 5734
2 2 10
1 368406 9714
2 368402 368407
1 64015 4680
2 64015 64003
1 152896 5381
1 152898 5974
1 152904 9158
1 152911 7250

368401
64011
152906

Hint

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$
$5$	$2\times10^5$

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