P6781 [Ynoi2008] rupq

Given a bracket sequence of length $n$. Each position has a bracket $a_i$, where $a_i=1$ means a left bracket `'('`, and $a_i=0$ means a right bracket `')'`. The bracket at position $i$ has a weight $b_i$. For any bracket sequence, by repeatedly deleting a substring of the form `'()'` until no more operations can be done, you will finally get a unique sequence. This sequence is called the unmatched brackets. For example, $a_1=')',a_2='(',a_3='(',a_4=')',a_5='('$: the unmatched bracket sequence is $')(('$, and the positions of these unmatched brackets are $1,2,5$. The corresponding $b$ values are $b_1,b_2,b_5$. There are $m$ operations, of the following three types: `1 x y`: Single-point modification, i.e. $a_x:=1-a_x; b_x:=y$. `2 l r`: For the unmatched bracket positions in $a[l..r]$, take the $\texttt {NAND}$ from left to right ($32$-bit bitwise NAND; see https://en.wikipedia.org/wiki/NAND_logic), and also take the $\texttt {max}$ (maximum value). Output the result of $\texttt {xor}$ between these two values. If the unmatched brackets form an empty sequence, then the answer for $\texttt {NAND}$ is $2^{32}-1$, and the answer for $\texttt {max}$ is $0$. $\texttt {NAND}$ means starting with $c_0=2^{32}-1$, then in order $c_i=\texttt {NAND}(c_{i-1},b_i)$. For a sequence $b$ with $n$ values, the final answer is $c_n$. `3 l r`: Swap $a[l..r]$ and $a[r+1..n]$. Do the same operation on $b$.

The first line contains two integers $n,m$ separated by spaces. Then $n$ lines follow, each containing two integers separated by spaces. The $i$-th line is $a_i,b_i$. Then $m$ lines follow, each describing one operation.

For each operation of type $2$, output one line with the answer.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477. For $100\%$ of the testdata, $0 \le a[i] \le 1$. $0 \le b[i] \le 10^9$. $1 \le n \le 2\times10^6,1 \le m \le 2\times10^5$。 Translated by ChatGPT 5