【链接】 我是链接,点我呀:)
【题意】
【题解】
对于1操作 令len = r-l+1 等价于查找l..r这个范围内**x的倍数的个数**是否大于等于len-1 也即l..r这个范围内**不是x的倍数的个数**小于等于1个 (因为**如果改的话,肯定是把那个数字改成x**,其他n-1个数**必须是x的倍数**,只有这样gcd才会为x (**不用改的情况**则**不一定里面就一定有x**,但**肯定都是x的倍数** (所以我们改的时候,实际上是一个**贪心**的过程,就**强行把那个不是x的倍数的数改成x** (或者是**虽然都是x的倍数,但gcd比x大,那么就任意把一个数字改成x就好了,gcd肯定就变成x了** (这样**加上"其他n-1个数字都是x的倍数"**这个限制,**整体的gcd就是x了**这个可以通过建立线段树来实现。
因为gcd有交换律。
所以合并的时候,只要把左边的gcd和右边的gcd一起求一个gcd就行了。
这样。我们在某个区间内。
设l..mid的gcd为xx
设mid+1..r的gcd为yy
如果gcd(xx,x)!=x 且 gcd(yy,x)!=x
也就是说左右两个子区间的gcd都不是x的倍数。
那么就直接返回无解。
(因为这就表示这两个区间分别有一个数字不是x的倍数,即不是x的倍数的个数>1,所以无解
如果gcd(xx,x)x且gcd(yy,x)x
就说明左右两个区间的gcd都是x的倍数。
那么这两个区间里面的数字肯定都是x的倍数。
也可以直接返回。
否则如果gcd(xx,x)!=x那么就往左区间继续递归。
如果gcd(yy,x)!=x那么就往右区间继续递归。
中间如果发现不是x的倍数的个数超过了1就直接退出
2操作就是线段树的单点更新。
【代码】
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rson m+1,r,rt<<1|1
#define lson l,m,rt<<1
using namespace std;
const int N=5e5+7;
int n,i,j,a[N],tr[N<<2],now,x;
void build(int l=1,int r=n,int rt=1)
{
if(l==r){
tr[rt]=a[l];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
tr[rt]=__gcd( tr[rt<<1] , tr[rt<<1|1]);
}
void query(int L,int R,int l=1,int r=n,int rt=1)
{
if (now>1) return;
int m=(l+r)>>1;
if(L<=l&&r<=R) {
if (l==r){
if (__gcd(tr[rt],x)!=x) now++;
return;
}
int xx = __gcd(tr[rt<<1],x),yy = __gcd(tr[rt<<1|1],x);
if (xx!=x && yy!=x){
now+=2;
return;
}else if (xx==x && yy==x) return;
if (xx!=x) query(L,R,lson);
if (yy!=x) query(L,R,rson);
return;
}
if (L<=m) query(L,R,lson);
if (m<R) query(L,R,rson);
}
void updata(int p,int num,int l = 1,int r = n,int rt = 1){
if (l==r){
a[l] = num;
tr[rt] = a[l];
return;
}
int m = (l+r)>>1;
if (p<=m)
updata(p,num,lson);
else
updata(p,num,rson);
tr[rt]=__gcd( tr[rt<<1] , tr[rt<<1|1]);
}
int main()
{
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >>n;
for (int i = 1;i <= n;i++) cin >>a[i];
build();
int Q;
cin >> Q;
while (Q--){
int ope;
cin >>ope;
if (ope==2){
int i,y;
cin >> i >> y;
updata(i,y);
}else{
int l,r;
cin >> l >> r >> x;
now = 0;
query(l,r);
if (now>1){
cout<<"NO"<<endl;
}else{
cout <<"YES"<<endl;
}
}
}
return 0;
}