Description：

给定一个正整数数列 $a_0, a_1, \dots, a_{n-1}$ ，你需要支持以下两种操作：

1. $MODIFY$ $id$ $x$ ：将 $a_{id}$ 修改为 $x$ 。 2. $QUERY$ $x$ : 求最小的整数 $p(0\le p<n)$ ，使得 $gcd(a_0, a_1, \dots, ap)\times xor(a_0, a_1, \dots, ap)= x$ 。其中 $xor(a_0, a_1, \dots, ap)$ 代表 $a_0, a_1, \dots, a_p$ 的异或和， $gcd$ 表示最大公约数。

数据范围： $n\le100000$ ， $q\le10000$ ， $a_i\le10^9(0\le i<n)$ ， $QUERY$ $x$ 中的 $x\le 10^{18}$ ， $MODIFY$ $id$ $x$ 中的 $0\le id<n$ ， $1\le x≤10^9$ .

Solution：

很明显 $gcd$ 是非严格递减的，那么我们处理出 $g[i]$ 表示从 $i$ 所在块的开头到 $i$ 的 $gcd$ ， $xor[i]$ 表示从 $i$ 所在块开头到 $i$ 的 $xor$ 。

假设暴力扫描，如果前面的块所取到的前缀 $gcd$ 为 $lastgcd$ ， $xor$ 为 $lastxor$ 。

若 $gcd(lastgcd,g[R[i]])==lastgcd$ ，则说明这个块内所有的数取 $gcd$ 后都是 $lastgcd$ ，那么

$xor[j]=(x/lastgcd)xor\ lastxor$ ，然后在 $map$ 中查找就可以了。

若不相等，那么暴力去扫描，因为每次取 $gcd$ 都会至少缩小两倍，所以最多 $O(log n)$ 次，所以复杂度是保证的。（这一步十分巧妙）。

修改操作，暴力修改所在块就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 100010

typedef long long ll;

ll a[MAXN];

#define MAXB 333

int L[MAXB],R[MAXB],belong[MAXN],tot;

map<ll,int> p[MAXB];

ll g[MAXN],sum[MAXN];

ll gcd(ll a,ll b){return (b == 0ll ? a : gcd(b,a % b));}

void build(int k)

{

	p[k].clear();

	ll pregcd = 0ll,prexor = 0ll;

	for(int i = L[k];i <= R[k];++i)

	{

		pregcd = g[i] = gcd(a[i],pregcd);

		prexor = sum[i] = (prexor ^ a[i]);

		if(p[k].find(sum[i]) != p[k].end())p[k][sum[i]] = min(p[k][sum[i]],i);

		else p[k][sum[i]] = i;

	}

	return;

}

void query(ll x)

{

	ll pregcd = 0ll,prexor = 0ll;

	for(int i = 1;i <= tot;++i)

	{

		if(gcd(g[R[i]],pregcd) == pregcd)

		{

			if(x % pregcd == 0)

			{

				if(p[i].find((x / pregcd) ^ prexor) != p[i].end())

				{

					printf("%d\n",p[i][(x / pregcd) ^ prexor] - 1);

					return;

				}

			}

		}

		else

		{

			for(int j = L[i];j <= R[i];++j)

			{

				if((prexor ^ sum[j]) * gcd(g[j],pregcd) == x)

				{

					printf("%d\n",j - 1);

					return;

				}

			}

		}

		prexor = (prexor ^ sum[R[i]]);

		pregcd = gcd(g[R[i]],pregcd);

	}

	puts("no");

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

		scanf("%lld",&a[i]);

	tot = sqrt(n);

	for(int i = 1;i <= tot;++i)

	{

		L[i] = (i - 1) * tot + 1;R[i] = i * tot;

		for(int j = L[i];j <= R[i];++j)

			belong[j] = i;

		build(i);

	}

	if(tot * tot < n)

	{

		L[tot + 1] = R[tot] + 1;R[tot + 1] = n;

		++tot;

		for(int j = L[tot];j <= R[tot];++j)

			belong[j] = tot;

		build(tot);

	}

	scanf("%d",&q);

	string s;

	ll x,y;

	for(int i = 1;i <= q;++i)

	{

		cin >> s;

		if(s == "QUERY")

		{

			scanf("%lld",&x);

			query(x);

		}

		else

		{

			scanf("%lld%lld",&x,&y);++x;

			a[x] = y;

			build(belong[x]);

		}

	}

	return 0;

}