/ WHOJ / 题库 /

[eJOI2019] 异或橙子

[eJOI2019] 异或橙子

题目描述

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

他一共扫描了 nn 个橙子,但有时他也会重新扫描一个橙子,导致这个橙子的 3232 位整数发生更新。

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

例如 l=2,u=4l=2,u=4 的情况,记橙子序列 AA 中第 ii 个橙子的整数是 ,那么他要求的就是:

a2a3a4(a2a3)(a3a4)(a2a3a4)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)

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

对于两个数的第 ii 位,记为 x,yx,y,那么:

xx yy xyx\oplus y
00 11 11
11 00 11
00 00 00
11 11 00

例:1323=2613\oplus 23=26

13=13= 00011010\cdots 001101
23=23= 00101110\cdots 010111
1323=13\oplus 23= 00110100\cdots 011010

格式

输入格式

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

接下来一行 nn 个非负整数,表示每个橙子扫描得到的数值 ,从 11 开始编号。

接下来 qq 行,每行三个数:

  • 如果第一个数是 11,接下来输入一个正整数 ii 与非负整数 jj,表示将第 ii 个橙子的扫描值 aia_i 修改为 jj

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

输出格式

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

样例1

样例输入1

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

样例输出1

2
0

样例2

样例输入2

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

2
5
4
4

样例1解释

  • 最初,A=[1,2,3]A=[1,2,3],询问结果为 123(12)(23)(123)=21\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=2

  • 修改后,第一个位置被修改为 33 ,询问的结果是 323(32)(23)(323)=03\oplus 2\oplus 3\oplus(3\oplus 2)\oplus (2\oplus 3)\oplus(3\oplus 2\oplus 3)=0