Bash and a Tough Math Puzzle [Codeforces Round #458 D]

http://codeforces.com/contest/914/problem/D

N要素の配列Aがあり、2種類のクエリに答える。
クエリ1 : A[l,r]のgcdがほぼxかどうか判定する
クエリ2 : A[i]をyに変更する

※gcdがほぼxである -> 区間の数を1つ以下変更してgcdをxにできる

前提知識

• セグメントツリー

解法

http://codeforces.com/contest/914/submission/34415355

セグメントツリーで解いていく。
セグメントツリーを割としっかり理解してないとクエリ1を理解できないかもしれない。
怪しい場合はセグメントツリーの簡単な問題をやってみよう。
　
まず普通にgcdのセグメントツリーを構築する。
クエリ2はこれで扱えるようになった。
　
クエリ1はこのセグメントツリー上でxの倍数でない要素の個数が何個あるかを取ってくればいい。
もし、xの倍数でない数の個数が0個か1個であればほぼgcdがxになる。
それ以上ならダメ。
今回はxの倍数でない要素の個数を取ってきたいが、0個か1個か2個以上のどれかだけ分かればいい。
これを使って枝刈りで通す。
　

int query(int x, int y, int g, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l) return 0;　　　　範囲外の場合はxの倍数でない数の個数は当然0を返す
        if (x <= l && r <= y) {　　　範囲が全てクエリの範囲内である場合は…
            if (val[k] % g == 0) return 0;　　その範囲のgcdがg(=x)の倍数ならば全てxの倍数なので0を返す
            if (l + 1 == r) return 1;　　　範囲に含まれる数が1つなら、xの倍数でない個数が1つなので1を返す
        }

        auto a = query(x, y, g, l, (l + r) / 2, k * 2);　　　右側のxの倍数でない個数を取ってくる
        if (2 <= a) return 2;　　　2個以上なら反対側を見るまでもなく2以上なので2を返す
        auto b = query(x, y, g, (l + r) / 2, r, k * 2 + 1);　　　左側のxの倍数でない個数を取ってくる
        return a + b;
    }

　
O(logN)以上掛かりそうだが、枝刈りのおかげなのか通る。

int gcd(int a, int b) { return a ? gcd(b%a, a) : b; }
#define def 0
template<class V, int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { return gcd(l,r); };
    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x,int y,int l=0,int r=NV,int k=1){if(r<=x||y<=l)return def;if(x<=l&&r<=y)return val[k];
    auto a=get(x,y,l,(l+r)/2,k*2);auto b=get(x,y,(l+r)/2,r,k*2+1);return comp(a,b);}
    void update(int i, V v) { i+=NV;val[i]=v;while(i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]); }
    void add(int i, V v) { update(i, val[i + NV] + v); }
    V operator[](int x) { return get(x, x + 1); }

    
    
    int query(int x, int y, int g, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l) return 0;
        if (x <= l && r <= y) {
            if (val[k] % g == 0) return 0;
            if (l + 1 == r) return 1;
        }

        auto a = query(x, y, g, l, (l + r) / 2, k * 2);
        if (2 <= a) return 2;
        auto b = query(x, y, g, (l + r) / 2, r, k * 2 + 1);
        return a + b;
    }
};
//---------------------------------------------------------------------------------------------------
int N, A[501010], Q;
SegTree<int, 1 << 19> st;
//---------------------------------------------------------------------------------------------------
#define yes "YES"
#define no "NO"
string query1(int l, int r, int x) {
    if (r - l + 1 == 1) return yes;
    int g = st.get(l, r + 1);
    if (g % x == 0) return yes;

    int cnt = st.query(l, r + 1, x);
    if (cnt == 1) return yes;
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) st.update(i, A[i]);
    cin >> Q;
    rep(q, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int l, r, x; cin >> l >> r >> x;
            l--; r--;
            printf("%s\n", query1(l, r, x).c_str());
        } else {
            int i, y; cin >> i >> y;
            i--;
            A[i] = y;
            st.update(i, y);
        }
    }