D Bash and a Tough Math Puzzle(线段树+思维+剪枝)

题目大意：
给你一个序列，你要在这个序列上进行 $m$m次操作，操作 $1:l,r,x$1:l,r,x表示判断是否序列区间 $[l,r]$[l,r]中所有数的 $gcd\left(\right)=x$gcd()=x，如果不等于你可以修改其中一个数的值。操作 $2:i,y将ai=y$2:i,y将ai=y。
思路：
注意到 $q=4e5$q=4e5也就是说你的所有操作要在 $O\left(logn\right)$O(logn)内完成才能通过这题，所以我们考虑采用线段树来解决这题。操作二比较简单就是基础的单点修改，我们来考虑一下操作一，当 $gcd(l,r)$gcd(l,r) mod $x=0$x=0也就是说这个区间内所有的数都是 $x$x的倍数，那么我们随便修改其中一个数为 $x$x，就会有整体的 $gcd=x$gcd=x.当一个区间 $gcd(li,ri)$gcd(li,ri) mod $x!=0$x!=0，也就是说这个区间至少有一个数不是 $x$x的倍数。但是我们无法确定是哪个数，所有我们需要递归要叶子节点才能确定，如果到达叶子节点并且这个节点 mod $x!=0$x!=0，说明要想使得 $gcd(l,r)=x$gcd(l,r)=x那么这个数必须要修改，我们用 $cnt$cnt来统计需要修改的节点个数。如果当前区间左右儿子都不是 $x$x的倍数必要要修改两个数，我们直接剪枝令 $cnt=2，return$cnt=2，return。最后根据 $cnt$cnt来输出就行了。
总结：线段树维护区间 $gcd$gcd。利用 $gcd$gcd性质剪枝以及思考，总体不是很难。还有需要注意的就是当一个区间 $gcd[li,ri]$gcd[li,ri] mod $x!=0$x!=0，需要一直递归到叶子节点才能判断，不能直接 $cnt++$cnt++，因为可能在某一个子区间有左右儿子 mod $x$x都不等于0。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
typedef long long int ll;
struct seg{
	int l,r;
	int gcd;
	seg(){}
	seg(int a,int b):l(a),r(b){}
}tree[maxn << 2];
void build(int id,int l,int r){
	tree[id] = {l,r};
	if(l == r){
		scanf("%d",&tree[id].gcd);
		return ;
	}
	int mid = l + r >> 1;
	build(id << 1,l,mid);
	build((id << 1) + 1,mid + 1, r);
	tree[id].gcd = __gcd(tree[id << 1].gcd,tree[(id << 1) + 1].gcd);
}	
void update(int id,int a,int b){
	if(tree[id].l == tree[id].r && tree[id].l == a){
		tree[id].gcd = b;
		return ;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	if(a <= mid)update(id << 1,a,b);
	else update((id << 1) + 1,a,b);
	tree[id].gcd = __gcd(tree[id << 1].gcd,tree[(id << 1) + 1].gcd);
}
void query(int id,int l,int r,int x,int &cnt){
	if(cnt >= 2){return;}	
	if(tree[id].l >= l && tree[id].r <= r){
		if(tree[id].gcd % x == 0)return ;
		else if(tree[id].l == tree[id].r){cnt++;return;}
		if(tree[id << 1].gcd % x != 0 && tree[(id << 1) + 1].gcd % x != 0){
			cnt = 2;return;
		}
		if(tree[id << 1].gcd % x != 0)
		query(id << 1,l,r,x,cnt);
		if(tree[(id << 1) + 1].gcd % x != 0)
		query((id << 1) + 1,l,r,x,cnt);
		return;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	if(r <= mid) query(id << 1,l,r,x,cnt);
	else if(l > mid) query((id << 1) + 1,l,r,x,cnt);
	else query(id << 1,l,r,x,cnt) , query((id << 1) + 1,l,r,x,cnt);
}
void solved(){
	int n;scanf("%d",&n);
	build(1,1,n);
	int q;scanf("%d",&q);
	int l,r,x;
	while(q--){
		int ins;scanf("%d",&ins);
		if(ins == 1){
			int cnt = 0;
			scanf("%d%d%d",&l,&r,&x);
			if(l == r){cout<<"YES"<<endl;continue;}
			query(1,l,r,x,cnt);
			if(cnt <= 1)printf("YES\n");
			else printf("NO\n");
		}
		if(ins == 2){
			ll i,y;
			scanf("%lld%lld",&i,&y);
			update(1,i,y);
		}
	}
}
int main(){
	solved();
	return 0;
}