题面看这里

题目大意

给你一个长度为 n 的数组 a，Grammy 和 Alice 用这个数组玩个小游（bo）戏（yi），游戏规则如下：

对于每局游戏，先选定一个位置 \(k\) 为起点，\(\rm Grammy\) 先手，轮流操作，每次操作都可以从当前位置 \(i\) 跳到后面的某个位置 \(j\)，\(j\) 满足 \(a_i\)​​​ 和 \(a_j\)​​​ 在二进制下最多只有一位不同，谁的回合中不能操作了，谁就输了。

然后有 m 次操作，每次操作给定两个数 op 和 k，op 代表操作类型，有两种：第一种类型，直接在数组末尾新增一个数 k；第二种类型，询问以 k 为起点开一局游戏谁能赢。

题目分析

首先显然这是一道博弈论的题目，于是我们从先手必胜态和先手必败态的分析入手。（以下简称必胜态和必败态）

必胜态的定义：可以跳到一个必败态的即为必胜态。

必败态的定义：没有一个地方可以跳或者能跳的地方都是必胜态的即为必败态。

打表，嗯推，推着推着发现一个有趣的性质：一个数如果在数组里面多次出现，那么除了最后出现的那个位置之外的其他位置都是必胜态。

设这个数为 \(x\)，\(x\) 最后出现的那个位置为 \(j\)​，分两种情况讨论。
1、当 \(j\) 为必胜态时，说明 \(j\) 后面有个可以跳的位置是必败态，则 \(j\) 前面的 \(x\) 也一定可以跳到这个位置从而达到必胜，此时 \(j\) 前面的 \(x\) 都是必胜态。
2、当 \(j\) 为必败态时，\(j\) 前面的 \(x\) 只需要跳到 \(j\) 这个必败态就可以达到必胜，此时 \(j\) 前面的 \(x\) 也都是必胜态。
综上，无论 \(j\) 是什么状态，\(j\) 前面的 \(x\) 都存在至少一种的必胜策略。

有了这个性质，对于任意一个数 x，我们就不必关心非最后的位置 j 以外的其他位置了，游戏开始位置为这些位置时直接输出 "Grammy" 即可。

对于某个数的最后一个位置 j，我们则需要判断一下这个究竟是必胜态还是必败态。

显然这个游戏没有平局，所以不是必胜态就是必败态，同时根据上面的定义，感性地觉着必胜态更好判一些，我们来思考怎么判断必胜态。

起始位置为终点时先手必定跳不动，所以最初的必败态是 k = n，初态在末尾，考虑逆着推。

想到一个正确性显然的算法：对于当前位置后面的每一个位置（逆着推的，后面的每一个位置的状态肯定都是确定好了的），判断其是否是必败态，如果是，再判断下能否跳过去，如果能跳过去，则当前的位置是必胜态，逆着推一直推到所求的位置 k 即可。

正确性显然，但复杂度不咋地，考虑到 a 数组很大，当起点 k 很小时，最坏时间复杂度 \(O(n^3),~n=2e5\)​​，必 T。

考虑优化，怎么优化捏，根据性质，易知只需判断每个数字出现的最后一个位置即可，因为我们要判的是后面某个位置是否为必败态，而除了每个数字的最后一个位置，其他位置都一定是必胜态，所以根本不用判，注意到数据范围 \(0\leq a_i\leq255\)​​​，因此每次游戏撑死也就判个 255 次，时间复杂度 \(O(n*255^2)\)​​​，当然还可以进一步优化，但这题时间开了 4s，且就算出题人特意造数据卡掉这个算法，我们也可以通过加点离线和特判来黑掉出题人造的数据，所以直接嗯艹过去就行了。大力出奇迹

代码实现

结合代码来说明一下实现细节。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
int a[maxn];
int vis[300],flag[300],v[300];
int main(){
	int n,m,op,k;
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		vis[a[i]]=i;
	}
	while(m--){
		cin >> op >> k;
		if(op==1){
			a[++n]=k;
			vis[k]=n;
		}
		else {
			if(vis[a[k]]>k){
				cout << "Grammy\n";
			}
			else {
				int cnt=0;
				for(int i=0;i<256;i++){
					flag[i]=0;
					if(vis[i]){
						v[cnt++]=vis[i];
					}
				}
				sort(v,v+cnt);
				for(int i=cnt-1;;i--){
					for(int j=i+1;j<cnt;j++){
						if(flag[a[v[j]]]==0){
							int d=a[v[i]]^a[v[j]];
							d&=d-1;
							if(d==0){
								flag[a[v[i]]]=1;
								break;
							}
						}
					}
					if(a[v[i]]==a[k]) break;
				}
				if(flag[a[k]]) cout << "Grammy\n";
				else cout << "Alice\n";
			}
		}
	}
}

vis[x] 用于储存数字 x 在数组 a 中的最后一个位置。

把真正要判的位置存在数组 v[] 中，排个序，然后 v[i] 就表示第 i 个真正要判的位置在原数组 a 中的下标；用 flag[i] 来标记 i 这个位置是必胜态还是必败态。

有个小技巧，判断能否跳过去可以 \(O(1)\)​ 判，代码如下：

int d=a[v[i]]^a[v[j]];
d&=d-1;
if(d==0) ;  //能跳
else ;  //不能跳

解释一下就是，两个数如果二进制下只有一位不同，那它们的异或和肯定是二的幂次，判断一个数 \(d\)​​ 是否是二的幂次只需判断 \(d~\&~(d-1)\)​ 是否为 0 即可。（可以举个栗子试试）