CodeForces - 914D gcd +线段树

一、内容

题意：给定一段区间，查询区间的gcd值是否是给出的，若是输出YES，不是输出NO，可以假定修改某一个值，并不是真正的修改序列中的这个值，而是在计算的时候认为是修改了。

二、思路

• 由于最多能改变一个数，所以我们先用线段树维护区间的gcd。然后在查询的时候，查询有多少值不能被给出的x整除， 若查询出的结果 <= 1代表 这多出来的1个可以修改，然后输出YES ，否则输出NO
• 因为一段区间的gcd都是给出的x的话， 那么这个区间里面的数都能被x整除，所以求出有几个不能被整除就能知道结果了。

三、代码

#include <cstdio>
const int maxn = 5e5 + 5;
int n, q, gc[maxn << 2], a[maxn], code, x, y, v;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
void build(int id, int l, int r) {
	if (l == r) {
		gc[id] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	gc[id] = gcd(gc[id << 1], gc[id << 1 | 1]);
}

void update(int id, int l, int r, int x, int v) {
	if (l == r) {
		gc[id] = v;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		update(id << 1, l, mid, x, v);
	} else {
		update(id << 1 | 1, mid + 1, r, x, v);
	}
	gc[id] = gcd(gc[id << 1], gc[id << 1 | 1]);	
}
//查询区间里面有多少个 不能被v整除 
int query(int id, int l, int r, int x, int y, int v) {

	if (l == r) {
		//判断这个数能不能作为v的倍数 
		
		return gc[id] % v == 0 ? 0 : 1;
	}
	int mid = (l + r) >> 1;
	int ans = 0; 	 
	if (x <= mid && gc[id << 1] % v != 0) {
		ans += query(id << 1, l, mid, x, y, v);
	}
	if (ans >= 2) return 2;
	if (y > mid && gc[id << 1 | 1] % v != 0) {
		ans += query(id << 1 | 1, mid + 1, r, x, y ,v);
	}
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	build(1, 1, n);
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		scanf("%d", &code);
		if (code == 1) {
			scanf("%d%d%d", &x, &y, &v);
			int ans = query(1, 1, n, x, y, v);
			if (ans > 1) {
				printf("NOn");
			} else {
				printf("YESn");
			}
		} else {
			scanf("%d%d", &x, &v);
			update(1, 1, n, x, v);
		}
	}
	return 0;
} 

最后

以上就是不安树叶为你收集整理的CodeForces - 914D gcd +线段树的全部内容，希望文章能够帮你解决CodeForces - 914D gcd +线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。