zcmimi's blog
查看原题

点击跳转

分块好题

\gcd有个性质: 一旦变动则小于原来的\frac 12(最小的质因子为2)

那么总共最多\log_2 n个不同的\gcd

每个块记录的信息:

  • 块内前缀gcd
  • 块内前缀xor和

然后对块内元素按前缀xor和排序

修改操作: 修改对应元素,并重构元素所在块

查询操作:

枚举每个块,若前缀gcd不变,则直接在排序好的元素中二分查找

否则枚举判断

复杂度O(n\sqrt n \log n)

#include<bits/stdc++.h>
const int N=100011;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int n,m,blk,a[N],bl[N],sx[N],sg[N],L[N],R[N];
struct node{
    int v,id;
    bool operator<(node t){
        return v!=t.v?v<t.v:id<t.id;
    }
}b[N];
void build(int k){
    int l=L[k],r=R[k];
    sg[l]=sx[l]=a[l];
    b[l]=(node){a[l],l};
    for(int i=l+1;i<=r;++i){
        sx[i]=sx[i-1]^a[i];
        sg[i]=gcd(sg[i-1],a[i]);
        b[i]=(node){sx[i],i};
    }
    std::sort(b+l,b+r+1);
}
typedef long long ll;
void ask(){
    ll v;scanf("%lld",&v);
    int ans=-1,G=a[1],X=0;
    for(int i=1;i<=bl[n]&&ans==-1;++i)
        if(gcd(sg[R[i]],G)!=G){
            for(int j=L[i];j<=R[i];++j){
                G=gcd(a[j],G),X^=a[j];
                if(1ll*G*X==v){ans=j;break;}
            }
        }
        else if(v%G==0){
            ll c=v/G^X;
            int l=L[i],r=R[i],p=l;
            while(l<=r){
                int m=l+r>>1;
                if(b[m].v>=c)p=m,r=m-1;
                else l=m+1;
            }
            if(b[p].v==c){ans=b[p].id;break;}
            G=gcd(sg[R[i]],G),X^=sx[R[i]];
        }
        else G=gcd(sg[R[i]],G),X^=sx[R[i]];
    if(ans==-1)puts("no");
    else printf("%d\n",ans-1);
}
int main(){
    scanf("%d",&n);blk=sqrt(n);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        bl[i]=(i-1)/blk+1;
        if(!L[bl[i]])L[bl[i]]=i;
        R[bl[i]]=i;
    }
    for(int i=1;i<=bl[n];++i)build(i);
    scanf("%d",&m);
    char opt[10];
    for(int i=1;i<=m;++i){
        scanf("%s",opt);
        if(opt[0]=='M'){
            int x,y;scanf("%d%d",&x,&y);
            ++x,a[x]=y,
            build(bl[x]);
        }
        else ask();
    }
}
LG 4108 [HEOI2015]公约数数列
comment评论
Search
search