题链：https://vjudge.net/problem/HDU-6610

题意：用到了尼姆博弈的结论。对于一个区间[L,R]，问有多少子区间[l,r],a[l] ^ a[l+1] ^ a[l+2] ^  ...  ^ a[r] ！= 0 ？ 有修改，修改是将a[pos],a[pos+1]交换。

思路：我们求等于0的子区间个数，再减去即可。CodeForces - 617E 的带修版。考虑修改带来的影响，首先因为前缀的思想，pre[pos-1]以及pre[pos+2] ,  pre[pos+3] , pre[pos+4] , ... , pre[n]都不会受影响。

修改前：

pre[pos]=pre[pos-1] ^ a[pos]

pre[pos+1] = pre[pos] ^ a[pos+1] = pre[pos-1] ^ a[pos] ^ a[pos+1]

修改后：

新的pre[pos] = pre[pos-1] ^ a[pos+1] = pre[pos-1] ^ a[pos]^a[pos] ^a[pos+1] = 旧的 pre[pos] ^a[pos] ^a[pos+1]  

新的 pre[pos+1] = 新的 pre[pos] ^ a[pos] =  pre[pos-1] ^ a[pos+1] ^ a[pos] = pre[pos-1] ^ a[pos] ^ a[pos+1] = 旧的 pre[pos+1]

我们可以发现只有pre[pos]发生了变化，变为了pre[pos]^a[pos]^a[pos+1] 。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
const int M = 2e6+10;
int n,m,a[N],pre[N];
struct node{int l,r,id,tim;
}q[N];
int cntq;
int b[N],cntb;
int base,be[N];
bool cmp(node a,node b){return (be[a.l]^be[b.l]) ? be[a.l]<be[b.l] :(be[a.r]^be[b.r]) ? be[a.r]<be[b.r] : a.tim<b.tim;
}
int num[M];
ll sum,ans[N],f[N];
void del(int x){--num[pre[x]];sum-=num[pre[x]];}
void add(int x){sum+=num[pre[x]];++num[pre[x]];
}
int read() {int res = 0;char c = getchar();while(!isdigit(c)) c = getchar();while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();return res;
}
int main(void){	for(ll i=1;i<N;i++)f[i]=i*(i+1)/2;//n=read(),m=read();while(scanf("%d%d",&n,&m)!=EOF){int maxx=0;cntq=cntb=0;base=ceil(pow(1.0*n,2.0/3.0));for(int i=1;i<=n;i++){a[i]=read();if(a[i]>maxx) maxx=a[i];pre[i]=pre[i-1]^a[i];be[i]=i/base;}for(int i=1;i<=m;i++){int op;op=read();if(op==1){q[++cntq].l=read();q[cntq].r=read();q[cntq].l--;q[cntq].id=cntq;q[cntq].tim=cntb;}elseb[++cntb]=read();}sort(q+1,q+1+cntq,cmp);sum=0;int l=1,r=0,ti=0;for(int i=1;i<=cntq;i++){			int ql=q[i].l,qr=q[i].r,qt=q[i].tim;while(l<ql) del(l++);while(l>ql) add(--l);while(r<qr) add(++r);while(r>qr) del(r--);			while(ti<qt){++ti;int pos=b[ti];if(ql<=pos&&pos<=qr)del(pos);				pre[pos]=pre[pos]^a[pos]^a[pos+1];swap(a[pos],a[pos+1]);if(ql<=pos&&pos<=qr)add(pos);}while(ti>qt){int pos=b[ti];if(ql<=pos&&pos<=qr)del(pos);				pre[pos]=pre[pos]^a[pos]^a[pos+1];swap(a[pos],a[pos+1]);if(ql<=pos&&pos<=qr)add(pos);--ti;}ans[q[i].id]=f[qr-ql]-sum;}for(int i=1;i<=cntq;i++)printf("%lld\n",ans[i]);maxx<<=1;for(int i=0;i<=maxx;i++)num[i]=0;}return 0;	
}