CF914D Bash and a Tough Math Puzzle

#include<bits/stdc++.h>

using namespace std;

using ll =long long ;

const int maxn=5e5+9;

struct Node{
    int l,r,v;
}tr[maxn<<2];

int gcd(int ma,int mi){return mi?gcd(mi,ma%mi):ma;}

int a[maxn],n,m,cnt;

void build(int l,int r,int now){
    if(l==r){
        tr[now].v=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1),build(mid+1,r,(now<<1)|1);
    tr[now].v=gcd(tr[now<<1].v,tr[(now<<1)|1].v);
}

void modify(int x,int l,int r,int now){
    if(l==r){
        tr[now].v=a[x];
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(x,l,mid,now<<1);
    else modify(x,mid+1,r,(now<<1)|1);
    tr[now].v=gcd(tr[now<<1].v,tr[(now<<1)|1].v);
}

void check(int l,int r,int now,int ll,int rr,int x){
    if(cnt>=2)return;
    if(l==r){
        if(tr[now].v%x)cnt+=1;
        return ;
    }
    if(tr[now].v%x==0)return ;
    int mid=(l+r)>>1;
    if(mid>=ll)check(l,mid,now<<1,ll,rr,x);
    if(mid<rr)check(mid+1,r,(now<<1)|1,ll,rr,x);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    build(1,n,1);
    cin>>m;
    for(int i=1,x,y,z,w;i<=m;++i){
        cin>>x>>y>>z;
        if(x&1){
            cnt=0;
            cin>>w;
            check(1,n,1,y,z,w);
            cout<<(cnt>=2?"NO\n":"YES\n");
        }else{
            a[y]=z;
            modify(y,1,n,1);
        }
    }
}