Codeforce 914 D. Bash and a Tough Math Puzzle 解析(線段樹、數論)

今天我們來看看CF914D
題目連結

題目
給你一個長度為$n$的數列$a$，每次玩家會選擇一個區間猜$g.c.d.$的值，或者改變數列中的某個數字。而猜中不一定要完全準確，如果玩家能夠改動一個區間中的數字讓$g.c.d.$完全猜中也是可以的。

前言

我對線段樹還是不熟阿，一開始一直感覺$g.c.d.$沒辦法用線段樹維護…

想法

上模板，從維護區間和的模板改成維護$g.c.d.$(這就是為什麼我code中的元素修改函式叫做$add$)。
接著注意到一件事，猜中的條件是:假設區間中有$k$個數字，只要其中$k-1$個數字可以被$val$($val\stackrel{def}{=}$玩家猜的數字)整除就可以了(如果這$k-1$個數字的$g.c.d.\ge val$，那麼只要把最後那個數字改成$val$就好)。
一開始我就直接這樣實作，每次從$root$開始往下找有幾個數字可以被整除，整個區間都看過以後再來檢查是否$\ge k-1$，但是發現這樣會TLE。
查網路後發現我們必須用一個全域變數去計算:有多少在區間中數字不可被整除，如果發現數量$>1$就要馬上跳離搜尋，如此一來就不會TLE了。
($almost$函式是這題的重點，寫法和模板有點差異，要小心實作。)

程式碼:

const int _n=5e5+10;  
int n,a[_n],q,tt,tot=0;  
namespace Seg{  
  int nn;  
  int t[_n<<2];  
  void pull(int v){t[v]=__gcd(t[2*v+1],t[2*v+2]);}  
  void apply(int v, int val){t[v]=val;}  
  void build(int v, int l, int r){  
    if(l+1==r)t[v]=a[l];  
    else{int m=(l+r)>>1;build(2*v+1,l,m),build(2*v+2,m,r);pull(v);}  
  }  
  void add(int v,int l,int r,int ql,int qr,int val){  
    if(r<=ql or qr<=l)return;  
    else if(ql<=l and r<=qr)apply(v,val);  
    else{  
      int m=(l+r)>>1;  
      add(2*v+1,l,m,ql,qr,val),add(2*v+2,m,r,ql,qr,val);  
      pull(v);  
    }  
  }  
  void add(int pos,ll val){add(0,0,nn,pos,pos+1,val);}  
  void init(int n_){nn=n_;build(0,0,nn);}  
  void almost(int v,int l,int r,int ql,int qr,int val){  
    if(tot>1)return;  
    if(r<=ql or qr<=l)return;  
    else if(ql<=l and r<=qr and t[v]%val==0)return;  
    else{  
      if(l+1==r){tot++;return;}  
      int m=(l+r)>>1;  
      almost(2*v+1,l,m,ql,qr,val),almost(2*v+2,m,r,ql,qr,val);  
    }  
  }  
}  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n;rep(i,0,n)cin>>a[i]; cin>>q;  
  Seg::init(n);  
  while(q--){  
    cin>>tt;  
    if(tt==1){  
      int l,r,x;cin>>l>>r>>x;l--,r--;  
      tot=0;Seg::almost(0,0,n,l,r+1,x);  
      if(tot<=1)cout<<"YES\n";  
      else cout<<"NO\n";  
    }else{  
      int i,y;cin>>i>>y;i--;  
      Seg::add(i,y);  
    }  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission