洛谷P6225 [eJOI2019] 异或橙子 题解

题目链接：P6225 [eJOI2019] 异或橙子

题意：

序列上有n个值，第i个值为Ai
一段区间[l,r]的异或和为 A(l)^..^A(r)
一段区间[l,r]的答案是把所有区间[i,j]的异或和结果异或起来(l<=i<=j<=r)
例如
区间[2,4]的答案为 A2^A3^A4^(A2^A3)^(A3^A4)^(A2^A3^A4)

现在给定m次操作：
第一种操作输入i,j,将Ai值修改为j
 第二种操作输入i,j,求区间[i,j]的答案

输入第一行为n,m
第二行n个值，为A1,...An
之后m行，
每一行输入操作的类型和对应的i,j

对于每个第二类操作，输出区间答案

n,m<=2e5

其实就是单点修改+查询下面这个柿子

$$\bigoplus_{i=l}^{r}\bigoplus_{j=i}^{r}a_j$$

考虑区间中一个数的出现次数

设 $l \le i \le r$ ，则 $i$ 在区间 $[l,r]$ 的异或和的异或和中出现的次数为

$$(i-l+1) \times (r-i+1)$$

推导过程：

包含 $i$ 的区间 $[l^{\prime},r^{\prime}]$一定满足 $l^{\prime} \le i \le r^{\prime}$

显然 $l^{\prime}$ 有 $i-l+1$ 种取值，$r^{\prime}$ 有 $r-i+1$ 种取值，易得上式。

根据异或的自反性，则 $i$ 的贡献取决于它出现次数的奇偶性

显然当 $(i-l+1)$ 和 $(r-i+1)$ 都为奇数时 $i$ 的出现次数为奇数

不难发现，此时 $i,l,r$ 同奇偶

故实际的贡献形如10101

考虑用两个树状数组，分别维护在奇、偶位置上的数的异或和

时间复杂度 $O(m \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

int n,Q,a[N];
int lowbit(int x){return x&(-x);}
struct BIT
{
    int tree[N];
    void add(int x,int v)
    {
        for(int i=x; i<=n; i+=lowbit(i))
            tree[i]^=v;
    }
    int sum(int x)
    {
        int res=0;
        for(int i=x; i; i-=lowbit(i))
            res^=tree[i];
        return res;
    }
}tr[2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i=1; i<=n; i++)
        cin >> a[i],tr[i&1].add(i,a[i]);
    for(int op,x,y; Q--;)
    {
        cin >> op >> x >> y;
        if(op==1) tr[x&1].add(x,a[x]^y),a[x]=y;
        else
        {
            if((x+y)&1) cout << "0\n";
            else cout << (tr[x&1].sum(y)^tr[x&1].sum(x-1)) << '\n';
        }
    }
    return 0;
}