题目地址：https://codeforces.com/contest/914/problem/D

题目：

给出序列，2种操作：

1 l r x： 判断是否可以通过修改[l,r]区间的一个数使该区间gcd=x，可以输出“YES”,否则“NO”

2 i y：把序列中的第i个值修改为y

 

解题思路：

首先建立区间gcd对应的线段树，对于第二种操纵，从下往上更新即可。

对于第一种操纵，因为只修改一个数，这个数可以不是x的倍数，若能输出YES，说明这个区间除该数外的其他数都必须是x的倍数，所以可以通过统计该区间内非x倍数的数的数目cnt来判断，若cnt>1则输出NO，否则YES。同时线段树上从上到下进行搜索时，若遇到一个区间的gcd是x的倍数，则无需再继续搜索下去。

 

ac代码：

要慢慢学会写格式规范的代码鸭( ´▽｀)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
#define lowbit(x) ((x) & (-x))
int n, q, type, L, R, x, y, pos;
int a[maxn], gd[4*maxn];
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void update(int id)
{
    gd[id] = gcd(gd[id << 1], gd[id << 1 | 1]);
}
void build(int l, int r, int id)
{
    if(l == r)
    {
        gd[id] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, id << 1);
    build(mid + 1, r,id << 1 | 1);
    update(id);
}
void change(int l, int r, int id, int pos, int y)
{
    if(l == r)
    {
        gd[id] = y;
        return ;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) change(l, mid, id << 1, pos, y);
    else change(mid + 1, r, id << 1 | 1, pos, y);
    update(id);
}
int  search(int l, int r, int id, int L, int R, int x)
{
    if(l ==  r)
        return gd[id] % x !=0;
    int mid = (l + r) >> 1;
    int cnt = 0;
    if((gd[id << 1] % x ) != 0 && L <= mid)//如果gd[id<<1]是x的倍数说明对应区间内的每个数都是x的倍数
    {
        cnt += search(l, mid, id << 1, L, R, x);
        if(cnt > 1) return cnt;//如果查询左半部分区间是cnt的值就已经大于1了，就没必要再查询右半部分了
    }
    if((gd[id << 1 | 1] % x) && R > mid)
    {
        cnt += search(mid + 1, r, id << 1 | 1, L, R, x);
        if(cnt > 1) return cnt;
    }
    return cnt;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
    //std::ios::sync_with_stdio(false);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, n, 1);
    scanf("%d", &q);
    for(int i = 1; i <= q; i++)
    {
        scanf("%d", &type);
        if(type==1)
        {
            scanf("%d %d %d", &L, &R, &x);
            int num = search(1, n, 1, L, R, x);
            if(num > 1) printf("NO\n");
            else printf("YES\n");
        }
        else
        {
            scanf("%d %d", &pos, &y);
            change(1, n, 1, pos, y);
        }
    }
    return 0;
}

【参考博客】：

https://blog.csdn.net/Link_Ray/article/details/89293465