给定一个数列$a_1,a_2,...,a_n$,支持两种操作
1 l r x,猜测数列中[l,r]位置上的数的最大公约数$x$，判断这个猜测是否是接近正确的。如果我们可以在数列[l,r]位置中改动至多一个数使得它们的最大公约数是x，那么这个猜测就被认为是接近正确的(注意我们不需要在数列中进行实际的改动)。如果这个猜测是接近正确的，输出"YES",否则输出"NO"(都不含引号)。
2 i y，将$a_i$的数值改为y。
如果这一段区间有超过一个数不是$x$的倍数就不行了，按照这一条直接写就行了，把gcd打错真是蠢哭
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 500010
#define ls node<<1
#define rs node<<1|1
using namespace std; int n,q;
int val[M<<],a[M]; int gcd(int x,int y) {return y==?x:gcd(y,x%y);} void update(int node)
{
if(!val[ls]||!val[rs]) val[node]=val[ls]+val[rs];
else val[node]=gcd(val[ls],val[rs]);
} void build(int node,int l,int r)
{
if(l==r) {val[node]=a[l];return;}
int mid=(l+r)/;
build(ls,l,mid);build(rs,mid+,r);
update(node);
} int query(int node,int l,int r,int l1,int r1,int x)
{
if(l1<=l&&r1>=r)
{
if(val[node]%x==) return ;
if(l==r) return (val[node]%x!=);
}
if(l1>r||r1<l) return ;
int ans=;
int mid=(l+r)/;
ans+=query(ls,l,mid,l1,r1,x);
if(ans>) return ans;
return ans+query(rs,mid+,r,l1,r1,x);
} void change(int node,int l,int r,int x,int k)
{
if(l==r) {val[node]=k;return;}
int mid=(l+r)/;
if(x<=mid) change(ls,l,mid,x,k);
else change(rs,mid+,r,x,k);
update(node);
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
build(,,n);
scanf("%d",&q);
while(q--)
{
int opt;
scanf("%d",&opt);
if(opt==)
{
int l,r,x;scanf("%d%d%d",&l,&r,&x);
printf(query(,,n,l,r,x)>?"NO\n":"YES\n");
}
else
{
int x,k; scanf("%d%d",&x,&k);
change(,,n,x,k);
}
}
return ;
}