CF1511G Chips on a Board

Description

https://www.luogu.com.cn/problem/CF1511G

Solution

很早之前模拟赛的题目，现在还是不会做。

这题套 nim 游戏的皮，想问我们只保留 $[L,R]$ 中的数的异或和是否为 $0$。

先开个桶把数都存下来。考虑倍增。令 $f_{i,j}$ 表示以 $i$ 为左端点，$i+2^j-1$ 为右端点。现在想要合并 $f_{i,j-1},f_{i+2^{j-1},j-1}$，观察到关于二进制下第 $j$ 位只与后面那一段的数的个数在第 $j$ 位下的奇偶有关，而如果以 $i$ 为左端点，那么第后面那一段第 $j$ 位下都为 $1$。所以计算后面那一段的个数即可。实现上可以用前缀和。

查询同理，每次合并都会给最后一段的距离加上一个二的幂次，前缀和讨论棋子的奇偶性即可。

倍增妙妙题，和二进制配合起来很棒啊

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 300005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int a[maxn],f[maxn][21],g[maxn][21],n,m,q;
signed main(void){
	int i,x,j,l,r;
	read(n);read(m);
	for (i=1;i<=n;i++) read(x),a[x]++;
	for (i=0;i<=m;i++) f[i][0]=a[i],g[i][0]=0;
	for (j=1;j<=20;j++) {
		for (i=0;i+(1<<j)-1<=m;i++) {
			f[i][j]=f[i][j-1]+f[i+(1<<j-1)][j-1];
			g[i][j]=g[i][j-1]^g[i+(1<<j-1)][j-1]^(f[i+(1<<j-1)][j-1]&1?(1<<j-1):0); 
		}
	}
	read(q);
	while (q--) {
		read(l);read(r);
		int ans1=0,ans2=0,now=0;
		for (i=20;i>=0;i--) 
			if (l+(1<<i)-1<=r) {
				ans1+=f[l][i];
				ans2^=g[l][i]^(f[l][i]&1?now:0);
				now+=(1<<i);l+=(1<<i);
			}
		putchar(ans2?'A':'B');
	}
	return 0;
}