P6225 [eJOI 2019] XOR Oranges

Janez likes oranges. He built an orange scanner, but for each scanned orange, the image output can only be a $32$-bit integer. He scanned a total of $n$ oranges, but sometimes he rescans an orange, causing the $32$-bit integer of that orange to be updated. Janez wants to analyze these oranges. He finds the XOR operation very interesting. Each time he chooses an interval from $l$ to $u$, and he wants to get the XOR of the XOR sums of all subintervals within this interval. For example, when $l=2,u=4$, let the integer of the $i$-th orange in the orange sequence $A$ be $a_i$. Then what he asks for is: $$a_2 \oplus a_3 \oplus a_4 \oplus (a_2\oplus a_3)\oplus(a_3\oplus a_4)\oplus(a_2\oplus a_3 \oplus a_4)$$ ------------------------------------- Note: $\oplus$ in the expression represents the bitwise XOR operation. The XOR rules are as follows. For the $i$-th bit of two numbers, denoted by $x,y$, we have: |$x$|$y$|$x\oplus y$| | :-----------: | :-----------: | :-----------: | |$0$|$1$|$1$| |$1$|$0$|$1$| |$0$|$0$|$0$| |$1$|$1$|$0$| Example: $13\oplus 23=26$ |$13=$|$0\cdots 001101$| | --------: | :------: | |$23=$|$0\cdots 010111$| |$13\oplus 23=$|$0\cdots 011010$|

The first line contains two positive integers $n,q$, representing the number of oranges and the number of operations. The next line contains $n$ non-negative integers, representing the value obtained by scanning each orange, indexed starting from $1$. The next $q$ lines each contain three numbers: - If the first number is $1$, then a positive integer $i$ and a non-negative integer $j$ follow, meaning to modify the scanned value $a_i$ of the $i$-th orange to $j$. - If the first number is $2$, then two positive integers $u,l$ follow, meaning to query the answer for this interval.

For each query, output one non-negative integer per line, representing the required total XOR sum.

#### Explanation of Sample Input/Output 1 - Initially, $A=[1,2,3]$, and the query result is $1\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=2$. - After the modification, the first position is changed to $3$, and the query result is $3\oplus 2\oplus 3\oplus(3\oplus 2)\oplus (2\oplus 3)\oplus(3\oplus 2\oplus 3)=0$. ---------------------------- #### Constraints **This problem uses bundled testdata with a total of 5 subtasks**. - Subtask 1 (12 points): $1\le n,q\le 10^2$, no special restrictions. - Subtask 2 (18 points): $1\le n,q\le 5\times 10^2$, and there are no update operations. - Subtask 3 (25 points): $1\le n,q\le 5\times 10^3$, no special restrictions. - Subtask 4 (20 points): $1\le n,q\le 2\times 10^5$, and there are no update operations. - Subtask 5 (25 points): $1\le n,q\le 2\times 10^5$, no special restrictions. For all testdata, $0\le a_i\le 10^9,1\le n,q\le 2\times 10^5$. -------------------------- #### Notes Original problem: [eJOI2019](http://ejoi2019.si/) Problem A. [XORanges](https://www.ejoi2019.si/static/media/uploads/tasks/xoranges-isc(1).pdf) Statement and data source: [LibreOJ](https://loj.ac/problem/3195) Translated by ChatGPT 5