打卡信奥刷题（3006）用C++实现信奥题 P6225 [eJOI 2019] 异或橙子

P6225 [eJOI 2019] 异或橙子

题目描述

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

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

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

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

a 2 ⊕ a 3 ⊕ a 4 ⊕ ( a 2 ⊕ a 3 ) ⊕ ( a 3 ⊕ a 4 ) ⊕ ( a 2 ⊕ a 3 ⊕ a 4 ) 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)a2​⊕a3​⊕a4​⊕(a2​⊕a3​)⊕(a3​⊕a4​)⊕(a2​⊕a3​⊕a4​)

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

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

例：13 ⊕ 23 = 26 13\oplus 23=2613⊕23=26

输入格式

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

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

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

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

• 如果第一个数是2 22，接下来输入两个正整数u , l 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]A=[1,2,3]，询问结果为1 ⊕ 2 ⊕ 3 ⊕ ( 1 ⊕ 2 ) ⊕ ( 2 ⊕ 3 ) ⊕ ( 1 ⊕ 2 ⊕ 3 ) = 2 1\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=21⊕2⊕3⊕(1⊕2)⊕(2⊕3)⊕(1⊕2⊕3)=2

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

数据规模与约定：

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

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

对于所有数据，0 ≤ a i ≤ 10 9 , 1 ≤ n , q ≤ 2 × 10 5 0\le a_i\le 10^9,1\le n,q\le 2\times 10^50≤ai​≤109,1≤n,q≤2×105

说明

原题来自：eJOI2019 Problem A. XORanges

题面&数据来自：LibreOJ

C++实现

#include<cstdio>usingnamespacestd;constintN=2e5+5;intn,q,a[N];#definelowbit(x)(x&(-x))structbit{intdat[N];inlinevoidupdate(intx,intp){for(;p<=n;p+=lowbit(p))dat[p]^=x;}inlineintxor_sum(intp){intx=0;for(;p;p-=lowbit(p))x^=dat[p];returnx;}};#undeflowbitbit tree[2];signedmain(){scanf("%d%d",&n,&q);for(registerinti=1;i<=n;i++)scanf("%d",a+i),tree[i&1].update(a[i],i);while(q--){intopt,x,y;scanf("%d%d%d",&opt,&x,&y);if(opt==1)tree[x&1].update(a[x]^y,x),a[x]=y;else{if((x+y)&1)printf("0\n");elseprintf("%d\n",tree[x&1].xor_sum(y)^tree[x&1].xor_sum(x-1));}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容