洛谷 P7096 [yLOI2020] 泸沽寻梦

题目背景

我应是泸沽烟水里的过客，
孑然弹铗，划天地开阖。
邂逅过的，梦醒之余，
却忘了该如何洒脱。

——银临《泸沽寻梦》

题目描述

南有仙地，名曰摩梭，摩梭有湖，泸沽是也。

茶茶在泸沽湖中寻找自己的梦。氤氲雾气中，茶茶的 nn 个梦排成了一个序列。茶茶的所有梦境都是拉瓦的样子。为了区分这些拉瓦，茶茶规定从左到右第 ii 个的拉瓦的美颜值是一个非负整数 a_ia**i。面对着这些梦，茶茶会进行 mm 次操作，每次操作会给定两个数字 p,xp,x，然后将 a_pa**p 和 a_{p+1}a**p+1 都对 xx 做按位异或。每次操作完之后，茶茶都想知道，当前的梦序列中，有多少个子区间 [l,r][l,r]，满足 l le rl≤r 且区间的异或和为 00，请你回答茶茶的问题。

区间 [l,r][l,r] 的异或和定义为 a_l otimes a_{l + 1} otimes dots a_{r - 1} otimes a_ra**l⊗a**l+1⊗…a**r−1⊗a**r。其中 otimes⊗ 代表二进制按位异或运算，即 C++ 语言的「^」运算符。两个区间不同当且仅当两区间左端点不同或两区间右端点不同或两区间左右端点均不同。

为了避免输出过大，你只需要输出四个整数，分别表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

输入格式

第一行有两个整数，分别表示梦境的数量 nn 和操作的次数 mm。
第二行有 nn 个用空格隔开的整数，第 ii 个整数表示第 ii 个拉瓦的美颜值 a_ia**i。
接下来 mm 行，每行两个整数，依次表示一次操作的 pp 和 xx。

输出格式

输出四行，每行一个整数，依次表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

题解：

异或的可差分性。这个修改很有特点，所以每次只需要单点修改前缀数组。

然后用一个unordered_map来维护这个桶。好写，常数小。map常数大因为它还带排序。

然后每次减去之前的贡献，加上新的贡献即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
long long s[N];
long long ans;
long long ansxor,ansj,ansmax=0,ansmin=1e18;
unordered_map <long long,int> mp;
int main()
{
	scanf("%d%d",&n,&m);
	mp[0]++;
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		s[i]=s[i-1]^a;
		ans+=mp[s[i]];
		mp[s[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		int p,x;
		scanf("%d%d",&p,&x);
		ans-=mp[s[p]]-1;
		mp[s[p]]--;
		s[p]^=x;
		ans+=mp[s[p]];
		mp[s[p]]++;
		ansxor^=ans;
		if(ans&1ll) 
			ansj++;
		ansmax=max(ansmax,ans);
		ansmin=min(ansmin,ans); 
	}
	printf("%lld
%lld
%lld
%lld
",ansxor,ansj,ansmax,ansmin);
	return 0;
}