問題

区間加算更新/区間GCD取得のクエリがたくさん与えられるので処理せよ

解法

差分のGCDを持っていい感じに。

GCD とする。 区間中のすべての に対し なのはすぐに気付ける。 となると差分のGCD から目的の を復元したくなる。 ここで実は任意の に対し が示せる。 実験してみて上手く引き当てればよい。 よって区間加算更新のsegment木と区間GCD取得のsegment木をそれぞれ持てば計算できる。

証明をしておこう。 を示せばよい。 前者はすべての に対し なのでそれら差分も で割り切れるため。 後者について。 を固定し任意の に対し を示せばよい。 議論は同様なので とおく。 である。 右辺の項はすべて で割り切れるため左辺もこれで割り切れる。 ただし でも問題ないことに注意。 これで示せた。

メモ

  • $$\mathrm{gcd}( a _ {l + 1} - a_l , \dots, a _ {r - 1} - a _ {r - 2} )$$ を実験してみるところまでは行ったが気付けなかった。実験コードがバグってたのが一因か
  • 「全てのメンテナンスを実施する日において、メンテナンス実施後、どの製造機も製造するクッキーの枚数が 枚以上 枚以下である。」これ罠だったりしそうと思ってたらどうやらそうらしい

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using ll = long long;
using namespace std;

template <class Monoid>
struct segment_tree {
    typedef typename Monoid::underlying_type underlying_type;
    int n;
    vector<underlying_type> a;
    const Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
    }
    void point_set(int i, underlying_type z) { // 0-based
        assert (0 <= i and i <= n);
        a[i + n - 1] = z;
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
        }
    }
    underlying_type range_concat(int l, int r) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        underlying_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
};
struct gcd_monoid {
    typedef ll underlying_type;
    ll unit() const { return 0; }
    ll append(ll a, ll b) const { return a and b ? __gcd(a, b) : a ? a : b; }
};

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    const OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n - 1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i - 1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i - n + 1] = op.apply(z, a[i - n + 1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
            range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
        }
    }
};
struct plus_operator_monoid {
    typedef ll underlying_type;
    typedef ll target_type;
    ll unit() const { return 0; }
    ll append(ll a, ll b) const { return a + b; }
    ll apply(ll a, ll b) const { return a + b; }
};

int main() {
    // init
    int n; cin >> n;
    dual_segment_tree<plus_operator_monoid> a(n, 0);
    REP (i, n) {
        int a_i; cin >> a_i;
        a.range_apply(i, i + 1, a_i);
    }

    segment_tree<gcd_monoid> delta(n - 1);
    REP (i, n - 1) {
        delta.point_set(i, abs(a.point_get(i + 1) - a.point_get(i)));
    }

    // query
    int m; cin >> m;
    while (m --) {
        int t, l, r; cin >> t >> l >> r;
        -- l;
        if (t) {
            a.range_apply(l, r, t);
            if (l > 0) delta.point_set(l - 1, abs(a.point_get(l) - a.point_get(l - 1)));
            if (r < n) delta.point_set(r - 1, abs(a.point_get(r) - a.point_get(r - 1)));

        } else {
            int d = a.point_get(l);
            if (r - l >= 2) {
                d = __gcd(d, (int)delta.range_concat(l, r - 1));
            }
            cout << d << endl;
        }
    }
    return 0;
}