原题链接

题目大意

给定长度为n的序列A，定义关于A的函数
$f(l,r) = a_l​⊕a_{l+1}​⊕⋯⊕a_r​$，
$F(l,r)=f(l,l)⊕f(l,l+1)⊕..⊕f(l,r)⊕f(l+1,l+1)⊕..⊕f(l+1,r)⊕..⊕f(r,r)$
定义两个操作：

  1. $0\space x\space y$代表将$A[x]$的值更改为$y$
  2. $1\space l\space r$代表需要计算$F(l,r)$的值

输出每一次第二个操作得到的结果

解题思路

对于$Xor$运算，肯定是判断每个元素次数的奇偶性，通过分析可以很快知道，对于函数$F(l,r)$:$若(r-l+1)为奇数则F(l,r)=A[l]⊕A[l+2]⊕A[l+4]⊕…⊕A[r]$
$若(r-l+1)为偶数则F(l,r)=0$
题目操作涉及到单点修改与区间求值，所以可以用树状数组处理，在每个节点上存储区间异或和，但是由A数组直接建立树状数组，对于求F函数的值时，区间不是连续的，所以可将A数组的奇数项与偶数项分别用两个树状数组来存储，使其连续。
对于单点修改的操作，相当于是先异或求改前的值去除影响，再将得到的结果与新值异或，所以我们可直接对相关节点直接异或$(A[x]⊕y)$

AC代码

样例输入

1
3 3
1 2 3
1 1 3
0 1 2
1 1 1

样例输出

Case #1:
2
2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;

long long a[1000002],c1[1000002],c2[1000002],tt,n,m;
long long lowbit(long long x)
{return x&(-x);}
void add1(long long i,long long x)
{
    while(i<=n)
    {
        c1[i]^=x;
        i+=lowbit(i);
    }
}
long long sum1(long long x)
{
    long long ans=0;
    while(x>0)
    {
        ans^=c1[x];
        x-=lowbit(x);
    }
    return ans;
}
void add2(long long i,long long x)
{
    while(i<=n)
    {
        c2[i]^=x;
        i+=lowbit(i);
    }
}
long long sum2(long long x)
{
    long long ans=0;
    while(x>0)
    {
        ans^=c2[x];
        x-=lowbit(x);
    }
    return ans;
}

int main(){
    scanf("%lld",&tt);
    for(long long ii=1;ii<=tt;++ii){
        scanf("%lld%lld",&n,&m);
        for(long long i=1;i<=n;++i){
            c1[i]=0;
            c2[i]=0;
        }
        for(long long i=1;i<=n;++i){
            scanf("%lld",&a[i]);
            if(i%2){
                add1((i+1)/2,a[i]);
            }
            else{
                add2((i)/2,a[i]);
            }
        }
        long long x,y,z;
        printf("Case #%lld:\n",ii);
        for(long long i=1;i<=m;++i){
            scanf("%lld%lld%lld",&x,&y,&z);
            if(x==1){
                if((z-y+1)%2){
                    if(y%2){
                        printf("%lld\n",sum1((z+1)/2)^sum1((y+1)/2-1));
                    }
                    else{
                        printf("%lld\n",sum2(z/2)^sum2(y/2-1));
                    }
                }
                else{
                    printf("0\n");
                }
            }
            else{
                if(y%2){
                    add1((y+1)/2,a[y]^z);
                }
                else{
                    add2(y/2,a[y]^z);
                }
                a[y]=z;
            }
            // cout<<"c1: ";
            // for(int i=1;i<=n;++i){
            //     cout<<c1[i]<<" ";
            // }
            // cout<<endl;
            // cout<<"c2: ";
            // for(int i=1;i<=n;++i){
            //     cout<<c2[i]<<" ";
            // }
            // cout<<endl;
        }
    }
    return 0;
}