自动搬运

查看原文

来自洛谷，原作者为

	Lice 这个人懒散惯了，什么都没写

搬运于2025-08-24 22:18:45，当前版本为作者最后更新于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$

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

$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)$

$=a_2\oplus a_4$（$4$ 个 $a_3$ 异或直接归零）

这样原来如此冗长的式子就很简单了。

再来几个：

• 当 $l=1,u=4$ 时，就是 $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