CF914D Bash and a Tough Math Puzzle 题解

题目链接：CF914D Bash and a Tough Math Puzzle

题意：

• 给定长度为 $n$ 的序列 $a$。$m$ 次操作。操作有两种：
  1. 1 l r x：若能在 $a_l\sim a_r$ 中 至多 修改一个数，使得 $\gcd(a_l,a_{l+1},\cdots,a_r)=x$，输出 YES，否则输出 NO。注意：我们不需要进行实际的改动。
  2. 2 i y：将 $a_i$ 修改为 $y$。
• $1\le n\le 5\times 10^5$，$1\le m\le 4\times 10^5$，$1\le a_i,x,y\le 10^9$。

设区间内不能被 $x$ 整除的数的个数为 $\text{cnt}$

• 若 $\text{cnt}=0$ ，则改不改无所谓
• 若 $\text{cnt}=1$ ，则直接把那个数修改为 $x$ 即可
• 若 $\text{cnt}>1$ ，则无解，输出NO

考虑用线段树维护区间 $\gcd$

查询时，只进入区间 $\gcd$ 能被 $x$ 整除的子结点

如果到达叶子就 ++cnt

时间复杂度 $O(n \log^2 n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(5e5+15)

int n,Q,cnt,seg[N<<2];
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void push_up(int at)
{
    seg[at]=gcd(seg[ls(at)],seg[rs(at)]);
}
void build(int l,int r,int at)
{
    if(l==r)
    {
        read(seg[at]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(at));
    build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int l,int r,int k,int at)
{
    if(l==r)
    {
        seg[at]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,l,mid,k,ls(at));
    else modify(x,mid+1,r,k,rs(at));
    push_up(at);
}
void query(int nl,int nr,int l,int r,int k,int at)
{
    if(cnt>1) return;
    if(l==r)
    {
        ++cnt;
        return;
    }
    int mid=(l+r)>>1;
    if(nl<=mid&&seg[ls(at)]%k) query(nl,nr,l,mid,k,ls(at));
    if(nr>mid&&seg[rs(at)]%k) query(nl,nr,mid+1,r,k,rs(at));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    build(1,n,1); read(Q);
    for(int op,x,y,z; Q--;)
    {
        read(op); read(x); read(y);
        if(op==1)
        {
            read(z);
            cnt=0,query(x,y,1,n,z,1);
            puts((cnt>1)?"NO":"YES");
        }else
        {
            modify(x,1,n,y,1);
        }
    }
    return 0;
}