题解 P6225 【[eJOI2019]异或橙子】

Lice · 2020-03-21 14:12:07 · 题解

Description

给定一个数列，长度为 n，第 i 项为 a_i。

两种操作：

• 单点修改

• 给定 l,u ，求 \large\oplus_{i=l}^{u}(\oplus_{j=i}^{u}a_j)

其中 \oplus_{i=l}^r a_i=a_l\oplus a_{l+1} \oplus \cdots \oplus a_r

Solution

本题的突破口： 异或的特殊性质

• a \oplus 0=a
• a\oplus a=0

那么对于原题目给的例子：

• 当 l=1,u=5 时，就是 a_1\oplus a_3\oplus a_5

手玩几下，发现点什么？

显然易见的一个结论：

• 当 l,u 奇偶性不同时，[l,u] 中所有元素都会对答案贡献偶数次 ，那么答案就是 0。

• 当 l,u 奇偶性相同时，[l,u] 中所有 l,u 奇偶性相同的位置的值会对答案贡献奇数次，其他位置的值则会贡献偶数次，那么答案就是 a_l \oplus a_{l+2} \oplus \cdots \oplus a_u。

实现？树状数组是个不错的选择。

我们保存两个树状数组，分别存奇数、偶数位置的信息。

详见代码。

Code

#include<cstdio>
using namespace std;

const int N=2e5+5;
int n,q,a[N];

#define lowbit(x) (x&(-x))
struct bit{
    int dat[N];
    inline void update(int x,int p){
        for(;p<=n;p+=lowbit(p)) dat[p]^=x;
    }
    inline int xor_sum(int p){
        int x=0;
        for(;p;p-=lowbit(p)) x^=dat[p];
        return x;
    }
};
#undef lowbit

bit tree[2];

signed main()
{
    scanf("%d%d",&n,&q);
    for(register int i=1;i<=n;i++)
        scanf("%d",a+i),tree[i&1].update(a[i],i);
    while(q--)
    {
        int opt,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");
            else printf("%d\n",tree[x&1].xor_sum(y)^tree[x&1].xor_sum(x-1));
        }
    }
    return 0;
}

最后来求个赞 QwQ