题解：CF914D Bash and a Tough Math Puzzle

这是一道几乎为模板的线段树裸题。题目要求的是单点更新，区间查询。

因为题目求的为 $\gcd$，所以线段树合并的时候肯定要写成 tree[cur] = gcd (tree[cur << 1],tree[cur << 1 | 1])，至于如何写 gcd (int x,int y) 函数，在此就不赘述。

首先讲区间查询。至多修改一个数，若能使其满足题意则输出 YES，否则为 NO。即修改的数为 $0$ 或 $1$ 时为 YES，其余情况均为 NO。和普通线段树的查询差不多，不过需要优化的有两个细节。一是当需要修改的数已经超过 $1$ 时，即可停止程序，因为答案此时一定为 NO；二是若整段的 $\gcd$ 已经为 $x$ 的倍数，也就是说至少把一个数修改为 $x$ 后就会满足题意，故可以停止程序之间输出 NO。

其次是单点修改，十分简单，几乎和模板的修改没有区别。唯一要注意的是在修改后，线段树的合并方式为 tree[cur] = gcd (tree[cur << 1],tree[cur << 1 | 1])，不要与 tree[cur] = tree[cur << 1] + tree[cur << 1 | 1] 混淆。

最后给一个完整代码：


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,cnt,a[MAX],tree[MAX << 2];
int gcd (int x,int y);
void build (int cur,int l,int r);
void query (int cur,int l,int r,int x,int y,int v);
void modify (int cur,int l,int r,int x,int v);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();
    for (int i = 1;i <= n;++i) a[i] = read ();
    build (1,1,n);
    m = read ();
    for (int i = 1;i <= m;++i)
    {
        int ty = read ();
        if (ty == 1)
        {
            int l = read (),r = read (),x = read ();
            cnt = 0;
            query (1,1,n,l,r,x);
            if (cnt > 1) printf ("NO\n");//需要修改的大于 1 则无法完成
            else printf ("YES\n");
        }
        else 
        {
            int x = read (),v = read ();
            modify (1,1,n,x,v);
        }
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
int gcd (int x,int y)//辗转相除
{
    if (x < y) swap (x,y);//确定大小
    return (y == 0) ? x : gcd (y,x % y);
}
void build (int cur,int l,int r)
{
    if (l == r)
    {
        tree[cur] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build (cur << 1,l,mid);
    build (cur << 1 | 1,mid + 1,r);
    tree[cur] = gcd (tree[cur << 1],tree[cur << 1 | 1]);
}
void query (int cur,int l,int r,int x,int y,int v)
{
    if (cnt > 1 || tree[cur] % v == 0) return ;//优化程序的地方
    if (l == r)
    {
        ++cnt;//需要改动的数的个数 + 1
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) query (cur << 1,l,mid,x,y,v);
    if (y > mid) query (cur << 1 | 1,mid + 1,r,x,y,v);
}
void modify (int cur,int l,int r,int x,int v)
{
    if (l == r && l == x)
    {
        tree[cur] = v;//单点修改
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify (cur << 1,l,mid,x,v);
    else modify (cur << 1 | 1,mid + 1,r,x,v);
    tree[cur] = gcd (tree[cur << 1],tree[cur << 1 | 1]);//合并方式要注意
}