自动搬运

查看原文

来自洛谷，原作者为

	hzoi_liuchang AFO

搬运于2025-08-24 22:26:36，当前版本为作者最后更新于2020-11-22 14:07:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

要求的是异或和等于 $0$ 的区间的个数

暴力枚举左右端点显然会 $T$ 飞

考虑将问题转化一下

设 $sum$ 数组为异或的前缀和

如果有 $a_l⊗a_{l+1}⊗…a_{r-1}⊗a_r=0$

那么就有 $sum[l-1]=sum[r]$

对于一个前缀和 $x$，如果一共有 $cnt$ 个前缀和和其相等

那么合法的方案数就是 $\frac{cnt(cnt+1)}{2}$

把前缀和扔进哈希表里，记录一下个数即可

考虑修改操作

如果把 $a[p]$ 和 $a[p+1]$ 都异或上 $x$

那么根据异或的性质 $x⊗x=0$

改变的只是 $sum[p]$，其它的都不变，相当于单点修改

在哈希表里随便改一下即可

时间复杂度 $O(n)$

目前是最优解

代码

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0; register char c = gc(); while(!isdigit(c)) c = gc(); while(isdigit(c)) x = x * 10 + (c & 15), c = gc(); x; })
char buf[1 << 20], *p1, *p2;
const int maxn=1e6+5;
const int mod=1e6+3;
int a[maxn],n,m;
long long ans1,ans2,ans3,ans4=0x3f3f3f3f3f3f3f3f,ans;
int sum[maxn],h[maxn],tot=1;
struct asd{
	int val,nxt,cnt;
}b[maxn*8];
long long js(int num){
	return 1LL*(num-1)*num/2;
}
void ad(int num,int val){
	rg int now=num%mod;
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		if(num==b[i].val){
			ans-=js(b[i].cnt);
			b[i].cnt+=val;
			ans+=js(b[i].cnt);
			return;
		}
	}
	b[tot].nxt=h[now];
	b[tot].val=num;
	b[tot].cnt=1;
	h[now]=tot++;
}
int main(){
	memset(h,-1,sizeof(h));
	n=read(),m=read();
	for(rg int i=1;i<=n;i++){
		a[i]=read();
	}
	ad(0,1);
	for(rg int i=1;i<=n;i++){
		sum[i]=sum[i-1]^a[i];
		ad(sum[i],1);
	}
	rg int aa,bb;
	for(rg int i=1;i<=m;i++){
		aa=read(),bb=read();
		ad(sum[aa],-1);
		sum[aa]^=bb;
		ad(sum[aa],1);
		ans1^=ans;
		if(ans&1) ans2++;
		ans3=max(ans,ans3);
		ans4=min(ans,ans4);
	}
	printf("%lld\n%lld\n%lld\n%lld\n",ans1,ans2,ans3,ans4);
	return 0;
}