我的思路是把原问题转化成有多少个前缀异或是0, 下面代码里 ed 数组表示该节点处是多少个前缀的结尾，las 数组表示的是每个前缀的结尾节点下标，dfs 是求未修改之前的 ans。

但是 ed 数组用 int 就会WA。 用 ull 就会 MLE，但是原来 WA 的点却 A 了， 难道结尾相同的前缀会超过 int 的范围吗？还是我其他的想法有问题 qwq。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
#define rint register int
typedef unsigned long long ull;
int n, m;
int sumxor[N], a; 
int ed[N*30];
ull mn = 9000000000000000000;
ull xans = 0, ans = 0, mx = 0;
int Trie[N*30][2], las[N], oddd = 0, tot = 0;
int xxx;char ccc;
inline int read()
{
	xxx = 0; ccc = getchar();
	while(!isdigit(ccc)) ccc = getchar();
	while(isdigit(ccc))
	{
		xxx = (xxx << 1) + (xxx << 3) + ccc - 48;
		ccc = getchar();
	}
	return xxx;
}
inline ull lmax(ull a, ull b)
{
	return a > b ? a : b;
}
inline ull lmin(ull a, ull b)
{
	return a < b ? a : b;
}
int c, fr;
inline void insert(ull x, int pos)
{
	fr = 0;
	for(rint i = 29; i >= 0; i--)
	{
		c = (x >> i)&1;
		if(!Trie[fr][c]) Trie[fr][c] = ++tot;
		fr = Trie[fr][c];
	}
	ed[fr]++;
	las[pos] = fr;
	return;
}

void dfs(int fr)
{
	if(ed[Trie[fr][0]] > 1) ans += (ed[Trie[fr][0]]) * (ed[Trie[fr][0]] - 1)/2 ;
	if(ed[Trie[fr][1]] > 1) ans += (ed[Trie[fr][1]]) * (ed[Trie[fr][1]] - 1)/2 ;
	if(Trie[fr][0]) dfs(Trie[fr][0]);
	if(Trie[fr][1]) dfs(Trie[fr][1]);
	return;
}

int main()
{
	n = read(), m = read();
	insert(0, 0);
	for(rint i = 1; i <= n; ++i)
	{
		a = read();
		sumxor[i] = sumxor[i - 1]^a;
		insert(sumxor[i], i);
	}
	dfs(0);
	int pos; 
	for(rint i = 1; i <= m; ++i)
	{
		pos = read(); a = read();
		ans += 1-ed[las[pos]];//删掉该前缀的一个贡献， 式子是ans = ans - (原贡献)*(原贡献-1)/2 + (原贡献-1)*(原贡献-2)/2
		ed[las[pos]]--;
		sumxor[pos] ^= a;
		insert(sumxor[pos], pos);
		ans += ed[las[pos]]-1;//加上新前缀的一个贡献， 也可以照上面推出来
		mx = lmax(mx, ans); mn = lmin(mn, ans);
		if(ans & 1) oddd++;
		xans ^= ans;
		if(ans < 0)printf("A");
		if(ed[las[pos]] < 0)printf("B");
		if(xans < 0)printf("C");
		if(sumxor[pos] < 0)printf("D");
	}
	printf("%llu\n%llu\n%llu\n%llu\n", xans, oddd, mx, mn);
    return 0;	
}