正题

题目链接:https://www.luogu.com.cn/problem/CF1511G

题目大意

给出\(n*m\)的棋盘上每一行有一个棋子，双方轮流操作可以把一个棋子向左移动若干步（不能不动），无法操作者输。

\(q\)次询问只留下期盼的\(l\sim r\)列时的胜负情况。

解题思路

右边界就是一个上限很好搞，但是左边界很麻烦，因为相当于让这些数都减去一个值。

因为二进制位下的，所以考虑一下一个类似于\(ST\)表的做法。设\(f_{i,j}\)表示留下\([i,i+2^j-1]\)的棋盘时的异或和。

合并的时候只需要多考虑一下在\([i+2^{j-1},i+2^j-1]\)位置的棋子数是奇数还是偶数就好了，如果是奇数还要多异或一个\(2^{j-1}\)。

然后询问的合并同理。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,q,f[N][19],s[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
f[x-1][1]^=1;s[x]^=1;
}
for(int i=1;i<=m;i++)s[i]^=s[i-1];
for(int j=2;(1<<j)<=m;j++)
for(int i=1;i+(1<<j)-1<=m;i++){
f[i][j]=f[i][j-1]^f[i+(1<<j-1)][j-1];
if(s[i+(1<<j)-1]^s[i+(1<<j-1)-1])f[i][j]^=(1<<j-1);
}
scanf("%d",&q);
while(q--){
int l,r,ans=0;
scanf("%d%d",&l,&r);
for(int j=18;j>=0;j--)
if(l+(1<<j)-1<=r){
ans^=f[l][j];l+=(1<<j);
if(s[r]^s[l-1])ans^=(1<<j);
}
if(ans)putchar('A');
else putchar('B');
}
return 0;
}