ARC017 D - ARCたんクッキー - Motsu_xe 競プロのhogeやfuga

ちょっと面白い問題だったので共有します。

問題概要

区間加算、区間gcd取得クエリを処理せよ。

思考&解法

まず遅延セグ木に載せてぇ*1となりますが、これは
$gcd(a+c,b+c) \neq gcd(a,b)+c$ なのでまあ普通に載りません。
まず部分点問題(一点更新、区間gcd取得クエリ)を考えると、これは普通にセグ木に載せることで解くことができます。
満点でも同じことをしたいなぁと思うと、区間加算というクエリが厄介になります。区間加算を単純化したいと思うと、よくあるのは階差を取るという方法です。階差を取ることで、区間加算は、2点加算へと単純化することができます。その上でどのように区間gcdを得るかを考えます。結局
$gcd(A_l,A_{l+1},..,A_r)=gcd(A_l,A_{l+1}-A_l,..,A_r-A_{r-1})$
となる*2ので、区間加算1点取得クエリで $A_l$ を、1点更新、区間gcd取得クエリで $gcd(A_{l+1}-A_l,..,A_r-A_{r-1})$ を得れれば問題を解くことができます。前者は双対セグ木*3、後者はセグ木で対応可能なので、解けました。

コード

#include<bits/stdc++.h>
using namespace std;

int gcd(int,int); //C++14だとstdに無い(1WA)

struct STree{//1点更新区間gcd用のセグ木
   STree(vector<int>&v) //vで初期化
   void update(size_t i, int x) //i番目にxを加算
   int get(size_t l, size_t r) //gcd(v_l,..,v_r-1)を取得
};

struct LST{ //区間加算1点取得用の遅延セグ木
    LST(vector<int>) //vector<int>で初期化
    void update(size_t l, size_t r, int x) //[l,r)にxを加算
    int get(size_t l, size_t r) //[l,r)の総和を取得
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m,t,l,r;
    cin>>n;
    vector<int> a(n),d(n-1);
    for(auto&i:a) cin>>i;
    for(int i{};i<n-1;++i) d[i]=a[i+1]-a[i];
    STree<int> st(d);
    LST<int> lst(a);
    cin>>m;
    for(int _{},_<m;++_){
        cin>>t>>l>>r;
        --l;
        if(t){
            lst.update(l,r,t);
            if(l) st.update(l-1,t);
            if(r<n) st.update(r-1,-t);
        }
        else cout<<gcd(lst.get(l,l+1),st.get(l,r-1))<<'\n';
    }
}