CF914D

用线段树乱搞一下就行qwq
#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int M = 3000001;

int n,m,k,a[M],d[M],al,ar,tp,s;

int gcd(int x,int y)

{

	if(!y) return x;

	return gcd(y,x%y);

}

void built(int now,int l,int r)

{

	if(l==r)

	{

		d[now]=a[l];

		return ;

	}

	int mid=(l+r)>>1;

	built(now*2,l,mid);

	built(now*2+1,mid+1,r);

	d[now]=gcd(d[now*2],d[now*2+1]);

}

void ask(int now,int l,int r,int L,int R,int k)

{

	if(l==r)

	{

		s++;

		return;

	}

	int mid=(l+r)>>1;

	if(L<=l && r<=R)

	{

		if(d[now]%k==0) return ;

		if(d[now*2]%k && d[now*2+1]%k) return s+=2,void();

		if(d[now*2]%k) ask(now*2,l,mid,L,R,k);

		else ask(now*2+1,mid+1,r,L,R,k);

		return ;

	}

	if(d[now*2]%k && L<=mid) ask(now*2,l,mid,L,R,k);

	if(s>1) return;

	if(d[now*2+1]%k && R>mid) ask(now*2+1,mid+1,r,L,R,k);

	return; 

}

void mody(int now,int l,int r,int x,int k)

{

	if(l==r) return d[now]=k, void();

	int mid=(l+r)>>1;

	if(x<=mid) mody(now*2,l,mid,x,k);

	else mody(now*2+1,mid+1,r,x,k);

	d[now]=gcd(d[now*2],d[now*2+1]);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	built(1,1,n);

	scanf("%d",&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%d",&tp);

		if(tp==1)

		{

			scanf("%d%d%d",&al,&ar,&k);

			s=0; ask(1,1,n,al,ar,k);

			if(s<2) printf("YES\n");

			else printf("NO\n");

		}

		else

		{

			scanf("%d%d",&al,&ar);

			mody(1,1,n,al,ar);

		}

	}

}
巴特西

CF914D

CF914D

最新文章

热门文章
