可以看出来两人的游戏是nim博弈 所以如果区间内的数异或和不为0 那么Alice 必胜
简单分析一下我们肯定要做一个前缀异或 然后再莫队就行 因为Bob会对序列进行修改 所以我们需要用带修莫队 然后就变成一个板子题目了
带修莫队 在块大小为 n^(2/3) 理论上复杂度最优
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5+10,M = 1e6+100; typedef long long ll; int xsum[N],p[N],sqn,a[N],blk; ll tx[M],ans[N],ret; struct node{ int l,r,t,id; bool operator < (const node &a)const{ if(l/blk!=a.l/blk) return l/blk<a.l/blk; if(r/blk!=a.r/blk) return r/blk<a.r/blk; return t<a.t; } }q[N]; void add(int x){ret+=tx[xsum[x]]++;} void del(int x){ret-=--tx[xsum[x]];} void upd(int i,int t){ int flag=(p[t]<=q[i].r&&p[t]>=q[i].l); if(flag) del(p[t]); xsum[p[t]]^=a[p[t]],swap(a[p[t]],a[p[t]+1]),xsum[p[t]]^=a[p[t]]; //printf("xsum=%d\n",xsum[p[t]]); if(flag) add(p[t]); } int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ memset(tx,0,sizeof(tx)); ret=0; blk=max(10,(int)pow(n,2./3)); int qcnt=0,kcnt=0; for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); xsum[i]=xsum[i-1]^a[i]; } for(int i = 1; i <= m; i++){ int op,l,r; scanf("%d%d",&op,&l); if(op==1){ scanf("%d",&r); q[++qcnt]=(node){l-1,r,kcnt,qcnt}; } else p[++kcnt]=l; } sort(q+1,q+1+qcnt); int l=1,r=0,T=0; for(int i = 1; i <= qcnt; i++){ while(l<q[i].l) del(l++); while(l>q[i].l) add(--l); while(r<q[i].r) add(++r); while(r>q[i].r) del(r--); while(T<q[i].t) upd(i,++T); while(T>q[i].t) upd(i,T--); ans[q[i].id]=1ll*(q[i].r-q[i].l)*(q[i].r-q[i].l+1)/2ll-ret; } for(int i = 1; i <= qcnt; i++) printf("%lld\n",ans[i]); } return 0; }
