题解
可以发现，(gcd(a_1,a_2,dots,a_{k+1})mid gcd(a_1,a_2,dots,a_k))，因此前缀中不同的 (gcd) 值只有 (log) 种。
考虑分块：每 (B) 个元素为一块，每块内维护区间异或和、区间内 (gcd) 的转折点和所有可能的前缀异或值。
查询时，枚举每个块，找到所有的转折点，进行 (log) 次形如“给定 (l,r,x)，查询最小的 (pin [l,r]) 使得 (operatorname{xor}_{1le kle p} a_k=x)”的询问。
若使用哈希表存储可能的异或值，则其修改的时间复杂度为 (mathcal{O}(Blog V))，查询的时间复杂度为 (mathcal{O}((B+frac{n}{B})log V))。
代码中采用的是排序后的 vector 代替哈希表，查询会多一个 (log)。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &_x){
_x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
_x*=_f;
}
template<typename T,typename... Args> void Read(T &_x,Args& ...others){
Read(_x);Read(others...);
}
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+5,SQ=505;
#define gcd __gcd
int n,q,a[N];
int bsiz,bcnt,bel[N];
struct Block{
int l,r,g,v;
vector<pii> chg,xo;
}bl[SQ];
void Update(int p){
int xo=0;
bl[p].g=bl[p].v=0;
bl[p].chg.clear(),bl[p].xo.clear();
For(i,bl[p].l,bl[p].r){
int temp=gcd(bl[p].g,a[i]);
if(temp!=bl[p].g) bl[p].chg.push_back({i,temp});
bl[p].g=temp,bl[p].v^=a[i];
xo^=a[i],bl[p].xo.push_back({xo,i});
}
sort(bl[p].xo.begin(),bl[p].xo.end());
}
void Init(){
bsiz=min(n,300);
for(int i=1;i<=n;i+=bsiz){
bl[++bcnt].l=i,bl[bcnt].r=min(n,i+bsiz-1);
}
For(i,1,bcnt){
For(j,bl[i].l,bl[i].r) bel[j]=i;
Update(i);
}
}
void Modify(int pos,int x){
a[pos]=x;
Update(bel[pos]);
}
pair<int,ll> Bf(ll x,int l,int r){
pair<int,ll> res{-1,0LL};
For(i,l,r){
res.second^=a[i];
if(res.first==-1&&res.second==x) res.first=i;
}
return res;
}
ll QXor(int l,int r){
if(l>r) return 0;
if(bel[l]==bel[r]) return Bf(-1,l,r).second;
ll res=Bf(-1,l,bl[bel[l]].r).second;
For(p,bel[l]+1,bel[r]-1) res^=bl[p].v;
res^=Bf(-1,bl[bel[r]].l,r).second;
return res;
}
int Find(ll x,int l,int r){
if(bel[l]==bel[r]) return Bf(x,l,r).first;
auto res1=Bf(x,l,bl[bel[l]].r);
if(res1.first!=-1) return res1.first;
x^=res1.second;
For(p,bel[l]+1,bel[r]-1){
auto it=lower_bound(bl[p].xo.begin(),bl[p].xo.end(),pii{x,-1});
if(it!=bl[p].xo.end()&&it->first==x){
return it->second;
}
x^=bl[p].v;
}
auto res2=Bf(x,bl[bel[r]].l,r);
return res2.first;
}
int Solve(ll x){
int g=0;vector<pii> chg;
For(p,1,bcnt){
if(bl[p].chg.empty()) continue;
auto fr=bl[p].chg.front();
if(p==1||gcd(g,fr.second)!=g) chg.push_back({fr.first,gcd(g,fr.second)});
for(auto it=next(bl[p].chg.begin());it!=bl[p].chg.end();++it){
if(gcd(it->second,g)==gcd(prev(it)->second,g)) continue;
chg.push_back({it->first,gcd(it->second,g)});
}
g=gcd(g,bl[p].g);
}
chg.push_back({n+1,0});
for(auto it=chg.begin();it!=prev(chg.end());++it){
if(x%it->second) continue;
ll goal=x/it->second;
goal^=QXor(1,it->first-1);
int res=Find(goal,it->first,next(it)->first-1);
if(res!=-1) return res;
}
return -1;
}
int main(){
Read(n);
For(i,1,n) Read(a[i]);
Init();
Read(q);
char temp[100];ll x;
while(q--){
scanf("%s",temp);Read(x);
if(temp[0]=='M'){
int k;Read(k);
Modify(x+1,k);
}else{
int ans=Solve(x);
if(ans!=-1) printf("%d
",ans-1);
else puts("no");
}
}
return 0;
}