记录编号	160573	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015]公约数数列	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	3.850 s
提交时间	2015-04-28 19:17:37	内存使用	4.37 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

#define maxm 400
#define maxn 100010
#define LL long long

map<LL, int>mp[maxm];
LL blo[maxm][maxm], gcd[maxm][maxm], exc[maxm][maxm];
int size, tot = 1, belong[maxn], len[maxm];

LL GCD(LL m, LL n) {
	LL r = m % n;
	while(r) {
		m = n, n = r, r = m % n;
	}
	return n;
}

void modify(int x, LL y) {
	int a = belong[x], b = x % size;
	if(!b) b = size;
	blo[a][b] = y, mp[a].clear();
	for(int i = 1; i <= len[a]; i++) {
		if(i == 1) {
			gcd[a][1] = exc[a][1] = blo[a][1];
			mp[a][exc[a][1]] = 1;
		} else {
			gcd[a][i] = GCD(gcd[a][i - 1], blo[a][i]);
			exc[a][i] = exc[a][i - 1] ^ blo[a][i];
			if(mp[a].count(exc[a][i])==0) mp[a][exc[a][i]] = i;
		}
	}
}

int query(LL y) {
	for(int i = 1; i <= len[1]; i++)
		if(gcd[1][i] * exc[1][i] == y) return i;
	LL last_gcd = gcd[1][size], last_xor = exc[1][size];
	for(int i = 2; i <= tot; i++) {
		if(last_gcd == GCD(last_gcd, gcd[i][len[i]]))
			if(mp[i].count((y / last_gcd) ^ last_xor)) return (i - 1) * size + mp[i][(y / last_gcd) ^ last_xor];
			else {
				last_xor ^= exc[i][len[i]]; continue;
			}
		for(int j = 1; j <= len[i]; j++)
			if((last_xor ^ exc[i][j]) * GCD(last_gcd, gcd[i][j]) == y) return (i - 1) * size + j;
		last_gcd = GCD(last_gcd, gcd[i][len[i]]), last_xor ^= exc[i][len[i]];
	}
	return 0;
}

int main() {
	freopen("gcdxor.in", "r", stdin);
	freopen("gcdxor.out", "w", stdout);
	int n;
	scanf("%d", &n); size = sqrt(n);
	for(int i = 1; i <= n; i++) {
		belong[i] = tot;
		if(i % size == 0 && i != n) tot++;
	}
	for(int i = 1; i <= n; i++) {
		int tmp = belong[i];
		scanf("%lld", &blo[tmp][++len[tmp]]);
		if(len[tmp] == 1) {
			gcd[tmp][1] = exc[tmp][1] = blo[tmp][1];
			mp[tmp][exc[tmp][1]] = 1;
		} else {
			gcd[tmp][len[tmp]] = GCD(gcd[tmp][len[tmp] - 1], blo[tmp][len[tmp]]);
			exc[tmp][len[tmp]] = exc[tmp][len[tmp] - 1] ^ blo[tmp][len[tmp]];
			if(mp[tmp].count(exc[tmp][len[tmp]])==0)mp[tmp][exc[tmp][len[tmp]]] = len[tmp];
		}
	}
	int q;
	scanf("%d", &q);
	char ch[20]; int x; LL y;
	for(int i = 1; i <= q; i++) {
		scanf("%s", ch);
		if(ch[0] == 'M') {
			scanf("%d%lld", &x, &y); x++;
			modify(x, y);
		} else {
			scanf("%lld", &y);
			int tmp = query(y);
			if(tmp) printf("%d\n", tmp - 1);
			else printf("no\n");
		}
	}
}