前言：毒瘤数据结构题，半个下午都在搞它了……
---------------------------
题目大意：给定一个长度为$n$的序列，有两种操作：1.把$a_x$的值改成$y$。2.求一个最小的$p$使得$gcd(a_0,a_1,cdots ,a_p)*XOR(a_0,a_1,cdots ,a_p)=x$。
------------------------------
这种数据结构题一般只能用分块解决。线段树什么的不得T飞……
对于每个块，我们维护块内的$gcd$和$xor$和，还要记录以每个块的左端点为左端点的$xor$前缀和。
修改的时候直接$sqrt n$暴力把所属块内的信息重新修改。
重点是查询。我们维护一个$pregcd$和$prexo$表示已经询问过的部分的$gcd$和$xor$和。有两种情况：
1.如果$gcd(pregcd,gcd[i])=pregcd$，那么二分查找块内可能符合条件的$p$。可以参考代码来理解。
2.如果不相等，那么暴力查找块内可能的$p$。
有一个性质：$A xor B=C$，那么$C xor B=A$。可以利用这个性质进行查询。
时间复杂度$O(nsqrt n log n)$。
代码：
/*记录每个块内的gcd，xor和；记录以每个块左端点为左端点的前缀xor和*/ #include<bits/stdc++.h> #define int long long using namespace std; int gcd[100005],sumxo[100005],n,m,a[100005],block,tot,pregcd,prexo; struct node{int sum,id;}xo[100005]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int GCD(int x,int y){if (!y) return x;return GCD(y,x%y);} bool cmp(node x,node y){if(x.sum==y.sum) return x.id<y.id;return x.sum<y.sum;} inline void build(int i) { gcd[(i-1)*block+1]=sumxo[(i-1)*block+1]=a[(i-1)*block+1]; xo[(i-1)*block+1]=(node){sumxo[(i-1)*block+1],(i-1)*block+1}; for (int j=(i-1)*block+2;j<=min(n,i*block);j++) { gcd[j]=GCD(gcd[j-1],a[j]); sumxo[j]=sumxo[j-1]^a[j]; xo[j]=(node){sumxo[j],j}; } sort(xo+(i-1)*block+1,xo+min(n,i*block)+1,cmp); } inline int half(int l,int r,int x) { int mid,res=l; while(l<=r) { mid=(l+r)>>1; if (xo[mid].sum>=x) res=mid,r=mid-1; else l=mid+1; } return res; } inline int query(int x) { int ans=-1; pregcd=a[1],prexo=0; for (int i=1;i<=tot&&ans==-1;i++) { if (GCD(pregcd,gcd[min(n,i*block)])==pregcd) { if (x%pregcd==0) { int k=(x/pregcd)^prexo; int pos=half((i-1)*block+1,min(n,i*block),k); if(xo[pos].sum==k) { ans=xo[pos].id; break; } } pregcd=GCD(pregcd,gcd[min(n,i*block)]),prexo^=sumxo[min(n,i*block)]; } else { for (int j=(i-1)*block+1;j<=min(n,i*block);j++) { pregcd=GCD(pregcd,a[j]);prexo^=a[j]; if (pregcd*prexo==x){ ans=j; break; } } if (ans!=-1) break; } } return ans; } signed main() { n=read();block=sqrt(n); tot=n/block;if (n%block) tot++; for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=tot;i++) build(i); m=read(); while(m--) { string s;cin>>s; if (s[0]=='M') { int x=read(),y=read();x++; a[x]=y; build((x-1)/block+1); } else { int x=read(); int s=query(x); if (s==-1) printf("no "); else printf("%lld ",s-1); } } return 0; }