题解 P4108 【[HEOI2015]公约数数列】

· · 题解

解题思路：

分块。

不同的前缀\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;
}