给定一个数列$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打错真是蠢哭
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define M 500010 5 #define ls node<<1 6 #define rs node<<1|1 7 using namespace std; 8 9 int n,q; 10 int val[M<<2],a[M]; 11 12 int gcd(int x,int y) {return y==0?x:gcd(y,x%y);} 13 14 void update(int node) 15 { 16 if(!val[ls]||!val[rs]) val[node]=val[ls]+val[rs]; 17 else val[node]=gcd(val[ls],val[rs]); 18 } 19 20 void build(int node,int l,int r) 21 { 22 if(l==r) {val[node]=a[l];return;} 23 int mid=(l+r)/2; 24 build(ls,l,mid);build(rs,mid+1,r); 25 update(node); 26 } 27 28 int query(int node,int l,int r,int l1,int r1,int x) 29 { 30 if(l1<=l&&r1>=r) 31 { 32 if(val[node]%x==0) return 0; 33 if(l==r) return (val[node]%x!=0); 34 } 35 if(l1>r||r1<l) return 0; 36 int ans=0; 37 int mid=(l+r)/2; 38 ans+=query(ls,l,mid,l1,r1,x); 39 if(ans>1) return ans; 40 return ans+query(rs,mid+1,r,l1,r1,x); 41 } 42 43 void change(int node,int l,int r,int x,int k) 44 { 45 if(l==r) {val[node]=k;return;} 46 int mid=(l+r)/2; 47 if(x<=mid) change(ls,l,mid,x,k); 48 else change(rs,mid+1,r,x,k); 49 update(node); 50 } 51 52 int main() 53 { 54 scanf("%d",&n); 55 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 56 build(1,1,n); 57 scanf("%d",&q); 58 while(q--) 59 { 60 int opt; 61 scanf("%d",&opt); 62 if(opt==1) 63 { 64 int l,r,x;scanf("%d%d%d",&l,&r,&x); 65 printf(query(1,1,n,l,r,x)>1?"NO\n":"YES\n"); 66 } 67 else 68 { 69 int x,k; scanf("%d%d",&x,&k); 70 change(1,1,n,x,k); 71 } 72 } 73 return 0; 74 }