You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Janez 喜欢橙子！他制造了一个橙子扫描仪，但是这个扫描仪对于扫描的每个橙子的图像只能输出一个 $32$ 位整数。

他一共扫描了 $n$ 个橙子，但有时他也会重新扫描一个橙子，导致这个橙子的 $32$ 位整数发生更新。

Janez 想要分析这些橙子，他觉得异或操作非常有趣，他每次选取一个区间从 $l$ 至 $u$，他想要得到这个区间内所有子区间的异或和的异或和。

例如 $l=2,u=4$ 的情况，记橙子序列 $A$ 中第 $i$ 个橙子的整数是 $a_i$，那么他要求的就是：

注：式子中的 $\oplus$ 代表按位异或运算。异或的运算规则如下。

对于两个数的第 $i$ 位，记为 $x,y$，那么：

例：$13\oplus 23=26$

输入格式

第一行输入两个正整数 $n,q$，表示橙子数量和操作次数。

接下来一行 $n$ 个非负整数，表示每个橙子扫描得到的数值 ，从 $1$ 开始编号。

接下来 $q$ 行，每行三个数：

• 如果第一个数是 $1$，接下来输入一个正整数 $i$ 与非负整数 $j$，表示将第 $i$ 个橙子的扫描值 $a_i$ 修改为 $j$。

• 如果第一个数是 $2$，接下来输入两个正整数 $u,l$ 表示询问这个区间的答案。

输出格式

对于每组询问，输出一行一个非负整数，表示所求的总异或和。

3 3
1 2 3
2 1 3
1 1 3
2 1 3

2
0

5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4

2
5
4
4

提示

输入输出样例 1 解释

• 最初，$A=[1,2,3]$，询问结果为 $1\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=2$

• 修改后，第一个位置被修改为 $3$ ，询问的结果是 $3\oplus 2\oplus 3\oplus(3\oplus 2)\oplus (2\oplus 3)\oplus(3\oplus 2\oplus 3)=0$。

数据规模与约定：

本题采用多测试点捆绑测试，共有 5 个子任务。

• Subtask 1(12 points)：$1\le n,q\le 10^2$，无特殊限制
• Subtask 2(18 points)：$1\le n,q\le 5\times 10^2$，且没有修改操作。
• Subtask 3(25 points)：$1\le n,q\le 5\times 10^3$，无特殊限制
• Subtask 4(20 points)：$1\le n,q\le 2\times 10^5$，且没有修改操作。
• Subtask 5(25 points)：$1\le n,q\le 2\times 10^5$，无特殊限制

对于所有数据，$0\le a_i\le 10^9,1\le n,q\le 2\times 10^5$

说明

原题来自：eJOI2019 Problem A. XORanges

题面&数据来自：LibreOJ