P6225 [eJOI 2019] 异或橙子题目描述Janez 喜欢橙子他制造了一个橙子扫描仪但是这个扫描仪对于扫描的每个橙子的图像只能输出一个32 3232位整数。他一共扫描了n nn个橙子但有时他也会重新扫描一个橙子导致这个橙子的32 3232位整数发生更新。Janez 想要分析这些橙子他觉得异或操作非常有趣他每次选取一个区间从l ll至u uu他想要得到这个区间内所有子区间的异或和的异或和。例如l 2 , u 4 l2,u4l2,u4的情况记橙子序列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那么x xxy yyx ⊕ y x\oplus yx⊕y0 001 111 111 110 001 110 000 000 001 111 110 00例13 ⊕ 23 26 13\oplus 232613⊕232613 13130 ⋯ 001101 0\cdots 0011010⋯00110123 23230 ⋯ 010111 0\cdots 0101110⋯01011113 ⊕ 23 13\oplus 2313⊕230 ⋯ 011010 0\cdots 0110100⋯011010输入格式第一行输入两个正整数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输入 #13 3 1 2 3 2 1 3 1 1 3 2 1 3输出 #12 0输入输出样例 #2输入 #25 6 1 2 3 4 5 2 1 3 1 1 3 2 1 5 2 4 4 1 1 1 2 4 4输出 #22 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题面数据来自LibreOJC实现#includecstdiousingnamespacestd;constintN2e55;intn,q,a[N];#definelowbit(x)(x(-x))structbit{intdat[N];inlinevoidupdate(intx,intp){for(;pn;plowbit(p))dat[p]^x;}inlineintxor_sum(intp){intx0;for(;p;p-lowbit(p))x^dat[p];returnx;}};#undeflowbitbit tree[2];signedmain(){scanf(%d%d,n,q);for(registerinti1;in;i)scanf(%d,ai),tree[i1].update(a[i],i);while(q--){intopt,x,y;scanf(%d%d%d,opt,x,y);if(opt1)tree[x1].update(a[x]^y,x),a[x]y;else{if((xy)1)printf(0\n);elseprintf(%d\n,tree[x1].xor_sum(y)^tree[x1].xor_sum(x-1));}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容