官方题解

题目大意

有 $n$ 盘饼干，双方轮流拿取，每次拿完后可以选择是否将剩余饼干合并到别的盘中，若最终无法拿取的人则输掉游戏。给出 $q$ 次询问，求出询问区间 $[l,r]$ 中有多少子段先手必胜。

题目思路

先考虑固定盘数时双方如何博弈。

若只有 $1$ 盘饼干，先手必胜。

若有 $2$ 盘饼干，谁把某一盘的饼干取完了谁就输了，所以每一盘饼干有一块是不能取的。不妨令 $a_i=a_i-1$ ，这样问题就变成 $nim$ 游戏问题，也就是说 $XOR_{i=l}^{r}(a_i-1)=0$ 的话，先手必败，反之先手必胜。

若有 $3$ 盘饼干，先手可以从最多的那盘取出若干饼干，将剩下的局面变成盘数为 $2$ 且上文提到的异或和为 $0$ 的情况，那么先手必胜。

若有 $4$ 盘饼干，谁先将盘数 $-1$ 谁就输了，所以还是看异或和是否为 $0$ 。

以此类推，不难发现，当堆数为奇数时，先手必胜，否则令 $a_i=a_i-1$ ，看异或和是否为 $0$ 。

所以我们只需要前缀异或，离线查询，用莫队求解。

时间复杂度 $O(n\sqrt{n})$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 2000010;

struct P{
    int l,r,id;
}qry[N];

int be[N],L[N],R[N];

bool cmp(P a,P b){
    if(be[a.l]!=be[b.l]) return be[a.l]<be[b.l];
    return be[a.r]<be[b.r];
}

int a[N],s[N];
int cnt[2][M];
long long sum;
void add(int x){
    sum+=cnt[x&1][s[x]];
    cnt[x&1][s[x]]++;
}
void del(int x){
    cnt[x&1][s[x]]--;
    sum-=cnt[x&1][s[x]];
}

long long ans[N];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]^(a[i]-1);
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        cin>>qry[i].l>>qry[i].r;
        qry[i].l--;
        qry[i].id=i;
    }
    
    int block=sqrt(n);
    int tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1;
        R[i]=min(n,i*block);
        for(int j=L[i];j<=R[i];j++) be[j]=i;
    }
    sort(qry,qry+q,cmp);

    long long l=1,r=0;
    for(int i=0;i<q;i++){
        P Q=qry[i];
        while(l>Q.l) add(--l);
        while(r<Q.r) add(++r);
        while(l<Q.l) del(l++);
        while(r>Q.r) del(r--);

        long long res=(r-l+1)*(r-l)/2-sum;
        ans[Q.id]=res;
    }

    for(int i=0;i<q;i++) cout<<ans[i]<<endl;
}