#P6225. [eJOI2019] 异或橙子

[eJOI2019] 异或橙子

题目描述

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

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

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

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

$$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
00 00
11

例: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 表示询问这个区间的答案。

输出格式

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

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]A=[1,2,3],询问结果为 $1\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=2$

  • 修改后,第一个位置被修改为 33 ,询问的结果是 $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):1n,q1021\le n,q\le 10^2,无特殊限制
  • Subtask 2(18 points):1n,q5×1021\le n,q\le 5\times 10^2,且没有修改操作。
  • Subtask 3(25 points):1n,q5×1031\le n,q\le 5\times 10^3,无特殊限制
  • Subtask 4(20 points):1n,q2×1051\le n,q\le 2\times 10^5,且没有修改操作。
  • Subtask 5(25 points):1n,q2×1051\le n,q\le 2\times 10^5,无特殊限制

对于所有数据,0ai109,1n,q2×1050\le a_i\le 10^9,1\le n,q\le 2\times 10^5


说明

原题来自:eJOI2019 Problem A. XORanges

题面&数据来自:LibreOJ