K 题题意:给定 堆石子,一次一个人选一堆非空的石子拿走至少一个石子,然后可以选择将这堆石子合并到其余非空的石堆去。 次询问,给定区间 ,问有多少个子区间 使得先手必胜。。
解法:当局面变成偶数堆时,先手不能合并操作使得堆数变成奇数(1),因而只能不断拿石子,这时后手也会做类似操作,因而堆数不变。当此时所有的堆(堆数仍为偶数)都变成了只有一个石子,那么先手必输——后手永远可以仿照先手的操作下对称棋。因而在偶数堆的局面下,先后手是可以一直玩对称棋的,直到抽到只剩一个石子为止,因而这个问题可以规约到每堆石子为 的 Nim 游戏。
(1)考虑为什么不能变成奇数堆——若变成奇数堆,后手一定可以从全部的堆中选出一堆,取走若干的石子,并执行合并操作,使得剩下的堆的石子个数减一 的异或和为 ,此时退化到堆的个数为偶数且异或和为 ,按照刚刚的分析这时先手必败,因而推导回两步之前那么先手就不能执行合并操作。
因而总结下来——奇数堆先手必胜,偶数堆 的异或和不为 则先手胜,否则后手胜。
那么维护 的异或前缀和,问题转化到了区间查询所有前缀值的出现位置(分奇偶讨论)和个数,因而可以使用莫队通过,时间复杂度 。
#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;
}