NC20015. [HEOI2015]公约数数列
描述
设计一个数据结构. 给定一个正整数数列 a0,a1,...,an−1，你需要支持以下两种操作：
MODIFY id x: 将 aid 修改为 x.
QUERY x: 求最小的整数 p(0≤p<n)，使得 gcd(a0,a1,...,ap)∗XOR(a0,a1,...,ap)=x. 其中 XOR(a0,a1,...,ap) 代表 a0,a1,⋯,ap 的异或和，gcd表示最大公约数。
输入描述
输入数据的第一行包含一个正整数 n.
接下来一行包含 n 个正整数 a0,a1,...,an−1。
之后一行包含一个正整数 q，表示询问的个数。
之后 q 行，每行包含一个询问。格式如题目中所述。
输出描述
对于每个 QUERY 询问，在单独的一行中输出结果。如果不存在这样的 p，输出 no.
示例1
输入:
10 1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640 10 MODIFY 7 20321280 QUERY 162343680 QUERY 1832232960000 MODIFY 0 92160 QUERY 1234567 QUERY 3989856000 QUERY 833018560 MODIFY 3 8600 MODIFY 5 5306112 QUERY 148900352
输出:
6 0 no 2 8 8
C++11(clang++ 3.9) 解法, 执行用时: 479ms, 内存消耗: 10232K, 提交时间: 2020-09-21 13:03:31
#include<bits/stdc++.h>
#define re register
#define il inline
#define int long long
using namespace std;
#define mp make_pair
template<typename T>il void read(T &ff){
T rr=1;ff=0;re char ch=getchar();
while(!isdigit(ch)){if(ch=='-')rr=-1;ch=getchar();}
while(isdigit(ch)){ff=(ff<<1)+(ff<<3)+(ch^48);ch=getchar();}
ff*=rr;
}
const int N=1e5+7,Siz=310,maxT=410;
#define B(i) ((i-1)/Siz+1)
#define Le(i) (i-1)*Siz
#define Ri(i) i*Siz-1
int n,T;
int a[N],xor1[N];
int queryX;
struct Block{
int L,R,len,tag, val[Siz],Gcd,Xor[Siz];
set<pair<int,int> > s;
il void getgcd(){Gcd=val[1];for(re int i=2;i<=len;++i)Gcd=__gcd(Gcd,val[i]);}
il void build(re int l,re int r){
L=l,R=r,len=r-l+1;
for(re int i=l;i<=r;++i)val[i-L+1]=a[i],Xor[i-L+1]=xor1[i],s.insert(mp(xor1[i],i-L+1));
getgcd();
}
il void change(re int x,re int y){
x=x-L+1; val[x]^=y;
for(re int i=x;i<=len;++i)s.erase(mp(Xor[i],i)),s.insert(mp(Xor[i]^=y,i));
getgcd();
}
il void get(re int x,re int &ans){
for(re int i=1;i<=len;++i){
x=__gcd(x,val[i]);
if(x*(Xor[i]^tag)==queryX)return ans=i+L-1,void();
}
}
il void find(re int x,re int &ans){
if(queryX%x)return;
auto it=s.lower_bound(mp((queryX/x)^tag,0));
if(it==s.end()||(it->first^tag)!=(queryX/x))return;
ans=it->second+L-1;
}
}b[maxT];
signed main(){
read(n);
T=B(n);
for(re int i=0;i<n;++i)read(a[i]),xor1[i]=xor1[i-1]^a[i];
for(int i=1;i<T;++i)b[i].build(Le(i),Ri(i)); b[T].build(Le(T),n-1);
char op[10]; int id,x;
int q; read(q); while(q--){
scanf("%s",op+1);
if(op[1]=='M'){
read(id),read(x);
const int c=a[id]^x; a[id]=x;
for(re int i=B(id)+1;i<=T;++i)b[i].tag^=c;
b[B(id)].change(id,c);
}else{
read(queryX);
int Gcd=0,ans=818181;
for(re int i=1;i<=T&&ans==818181;++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==818181)puts("no");
else printf("%lld\n",ans);
}
}
return 0;
}