自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 21:56:35，当前版本为作者最后更新于2019-02-18 13:45:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路：

分块。

不同的前缀$\gcd$有$O(\log a)$个，每次变化至少缩小到原来的一半。

设块大小为$S$，我们需要维护的信息有：每个块的块内$\gcd$，每个位置作为结尾的前缀异或和。

考虑修改一个数，我们转化为对一个数异或上另一个数$x$，则这个数及其之后的数的前缀异或和都会异或上$x$，块内暴力修改，区间打tag即可。

用set把前缀异或和存起来。单次修改复杂度$O(S\log n+\frac{n}{S})$。

考虑查询，我们从左往右扫描每个块，维护当前前缀$\gcd$。

若和一个新的块$\gcd$后，其值改变，则说明这个块内有前缀$\gcd$不同的位置。直接暴力扫描整块即可。如果没改变，则其前缀$\gcd$都相同，直接在set上二分即可。

由于块内暴力还要求$\gcd$，共有$O(\log a)$个这样的块。单次查询复杂度$O(S\log^2 a+\frac{n\log S}{S})$。

Code：

#include<cstdio>
#include<algorithm>
#include<set>
const int N=100005,siz=318;
#define gcd std::__gcd
#define bel(x)((x-1)/siz+1)
#define mp std::make_pair
typedef long long LL;
int n,m,K,a[N],xp[N];
LL qry;
struct BLOCK{
	int val[320],L,R,len,Gcd,Xor[320],tag;
	std::set<std::pair<int,int>>s;
	void re(){
		Gcd=val[1];
		for(int i=2;i<=len;++i)Gcd=gcd(Gcd,val[i]);
	}
	void build(int l,int r){
		L=l,R=r,len=r-l+1;
		for(int i=l;i<=r;++i)val[i-l+1]=a[i],Xor[i-l+1]=xp[i],s.insert(mp(xp[i],i-l+1));
		re();
	}
	void modify(int pos,int dlt){
		pos=pos-L+1;
		for(int i=pos;i<=len;++i){
			s.erase(mp(Xor[i],i));
			s.insert(mp(Xor[i]^=dlt,i));
		}
		val[pos]^=dlt;
		re();
	}
	void get(int gg,int&ans){
		for(int i=1;i<=len;++i){
			gg=gcd(gg,val[i]);
			if((LL)gg*(Xor[i]^tag)==qry){
				ans=L+i-1;
				return;
			}
		}
	}
	void find(int gg,int&ans){
		if(qry%gg!=0)return;
		auto it=s.lower_bound(mp((qry/gg)^tag,0));
		if(it==s.end()||(it->first^tag)!=(qry/gg))return;
		ans=it->second+L-1;
	}
}b[320];
int main(){
	scanf("%d",&n);
	K=bel(n);
	for(int i=0;i<n;++i)scanf("%d",a+i),xp[i]=xp[i-1]^a[i];
	for(int i=1;i<K;++i)b[i].build((i-1)*siz,i*siz-1);
	b[K].build((K-1)*siz,n-1);
	for(scanf("%d",&m);m--;){
		char opt[12];
		scanf("%s",opt);
		if(*opt=='M'){
			int pos,x;
			scanf("%d%d",&pos,&x);
			const int dlt=a[pos]^x;a[pos]=x;
			for(int i=bel(pos)+1;i<=K;++i)b[i].tag^=dlt;
			b[bel(pos)].modify(pos,dlt);
		}else{
			scanf("%lld",&qry);
			int Gcd=0,ans=666666;
			for(int i=1;i<=K&&ans==666666;++i){
				int lst=Gcd;
				Gcd=gcd(Gcd,b[i].Gcd);
				if(Gcd!=lst)b[i].get(lst,ans);else
				b[i].find(Gcd,ans);
			}
			if(ans==666666)puts("no");else
			printf("%d\n",ans);
		}
	}
	return 0;
}