题目描述
Janez 喜欢橙子!他制造了一个橙子扫描仪,但是这个扫描仪对于扫描的每个橙子的图像只能输出一个 32 位整数。
他一共扫描了 n 个橙子,但有时他也会重新扫描一个橙子,导致这个橙子的 32 位整数发生更新。
Janez 想要分析这些橙子,他觉得异或操作非常有趣,他每次选取一个区间从 l 至 u,他想要得到这个区间内所有子区间的异或和的异或和。
例如 l=2,u=4 的情况,记橙子序列 A 中第 i 个橙子的整数是 ai,那么他要求的就是:
a2⊕a3⊕a4⊕(a2⊕a3)⊕(a3⊕a4)⊕(a2⊕a3⊕a4)
注:式子中的 ⊕ 代表按位异或运算。异或的运算规则如下。
对于两个数的第 i 位,记为 x,y,那么:
x |
y |
x⊕y |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
例:13⊕23=26
13= |
0⋯001101 |
23= |
0⋯010111 |
13⊕23= |
0⋯011010 |
输入格式
第一行输入两个正整数 n,q,表示橙子数量和操作次数。
接下来一行 n 个非负整数,表示每个橙子扫描得到的数值 ,从 1 开始编号。
接下来 q 行,每行三个数:
-
如果第一个数是 1,接下来输入一个正整数 i 与非负整数 j,表示将第 i 个橙子的扫描值 ai 修改为 j。
-
如果第一个数是 2,接下来输入两个正整数 u,l 表示询问这个区间的答案。
输出格式
对于每组询问,输出一行一个非负整数,表示所求的总异或和。
提示
输入输出样例 1 解释
-
最初,A=[1,2,3],询问结果为 1⊕2⊕3⊕(1⊕2)⊕(2⊕3)⊕(1⊕2⊕3)=2
-
修改后,第一个位置被修改为 3 ,询问的结果是 3⊕2⊕3⊕(3⊕2)⊕(2⊕3)⊕(3⊕2⊕3)=0。
数据规模与约定:
本题采用多测试点捆绑测试,共有 5 个子任务。
- Subtask 1(12 points):1≤n,q≤102,无特殊限制
- Subtask 2(18 points):1≤n,q≤5×102,且没有修改操作。
- Subtask 3(25 points):1≤n,q≤5×103,无特殊限制
- Subtask 4(20 points):1≤n,q≤2×105,且没有修改操作。
- Subtask 5(25 points):1≤n,q≤2×105,无特殊限制
对于所有数据,0≤ai≤109,1≤n,q≤2×105
说明
原题来自:eJOI2019 Problem A. XORanges
题面&数据来自:LibreOJ