牛客多校第七场 K 题题解

K 题题意：给定 $n$ 堆石子，一次一个人选一堆非空的石子拿走至少一个石子，然后可以选择将这堆石子合并到其余非空的石堆去。 $q$ 次询问，给定区间 $[L, R]$ ，问有多少个子区间 $[l,r] \subset [L,R]$ 使得先手必胜。 $n,q \leq 1\times 10^5$ 。

解法：当局面变成偶数堆时，先手不能合并操作使得堆数变成奇数（1），因而只能不断拿石子，这时后手也会做类似操作，因而堆数不变。当此时所有的堆（堆数仍为偶数）都变成了只有一个石子，那么先手必输——后手永远可以仿照先手的操作下对称棋。因而在偶数堆的局面下，先后手是可以一直玩对称棋的，直到抽到只剩一个石子为止，因而这个问题可以规约到每堆石子为 $a_{i} - 1$ 的 Nim 游戏。

（1）考虑为什么不能变成奇数堆——若变成奇数堆，后手一定可以从全部的堆中选出一堆，取走若干的石子，并执行合并操作，使得剩下的堆的石子个数减一 $a_{i} - 1$ 的异或和为 $0$ ，此时退化到堆的个数为偶数且异或和为 $0$ ，按照刚刚的分析这时先手必败，因而推导回两步之前那么先手就不能执行合并操作。

因而总结下来——奇数堆先手必胜，偶数堆 $a_{i} - 1$ 的异或和不为 $0$ 则先手胜，否则后手胜。

那么维护 $a_{i} - 1$ 的异或前缀和，问题转化到了区间查询所有前缀值的出现位置（分奇偶讨论）和个数，因而可以使用莫队通过，时间复杂度 $\mathcal O(n \sqrt n)$ 。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+10,M=3e6+3;
int n,m,bel[N],col[N],t,len;
LL sum[2],c[2][M];
struct hh{
	int l,r,pos;
	bool operator<(const hh a) const{
	return (bel[l]^bel[a.l])?bel[l]<bel[a.l]:r<a.r;}
}a[N];
LL ans[N];
int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
void init()
{
	n=in()+1,m=in();
	for(int i=2;i<=n;++i) col[i]=in()-1;
	for(int i=2;i<=n;++i) col[i]^=col[i-1];
	for(int i=1;i<=m;++i){
		a[i].l=in(),a[i].r=in()+1,a[i].pos=i;
		int len=a[i].r-a[i].l;
		ans[i]=1ll*(a[i].r-a[i].l)*(a[i].r-a[i].l-1)/2+len;
	}  
}
void pre()
{
	t=sqrt(n),len=n/t;
	for(int i=1;i<=t;++i) 
	  for(int j=(i-1)*len+1;j<=i*len;++j) bel[j]=i;
	if(t*len<n){
		for(int j=t*len+1;j<=n;++j) bel[j]=t+1;
		++t;
	}
	sort(a+1,a+m+1);  
}
void solve()
{
	int l,r,j=1;
	for(int i=1;i<=t;++i)
	{
		l=(i-1)*len+1,r=l-1,sum[0]=sum[1]=0;
		for(;bel[a[j].l]==i;++j)
        {
        	while(r<a[j].r) ++r,sum[r&1]+=(++c[r&1][col[r]])-1;
        	while(l>a[j].l) --l,sum[l&1]+=(++c[l&1][col[l]])-1;
        	while(l<a[j].l) sum[l&1]-=(c[l&1][col[l]]--)-1,++l;
        	ans[a[j].pos]-=(sum[0]+sum[1]);
		}
		for(int k=1;k<=n;++k) c[k&1][col[k]]=0;
	}
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
}
int main()
{
	init();
	pre();
	solve();
	return 0;
}