結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー suisensuisen
提出日時 2024-01-31 03:26:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 427 ms / 5,000 ms
コード長 12,844 bytes
コンパイル時間 1,050 ms
コンパイル使用メモリ 86,068 KB
実行使用メモリ 12,824 KB
最終ジャッジ日時 2024-09-28 10:19:38
合計ジャッジ時間 12,086 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 4 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 4 ms
6,944 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 408 ms
12,076 KB
testcase_12 AC 398 ms
12,240 KB
testcase_13 AC 279 ms
12,088 KB
testcase_14 AC 387 ms
12,684 KB
testcase_15 AC 408 ms
12,640 KB
testcase_16 AC 427 ms
12,564 KB
testcase_17 AC 368 ms
12,772 KB
testcase_18 AC 360 ms
12,756 KB
testcase_19 AC 314 ms
12,584 KB
testcase_20 AC 313 ms
12,764 KB
testcase_21 AC 323 ms
12,616 KB
testcase_22 AC 315 ms
12,528 KB
testcase_23 AC 322 ms
12,624 KB
testcase_24 AC 276 ms
12,656 KB
testcase_25 AC 280 ms
12,700 KB
testcase_26 AC 283 ms
12,404 KB
testcase_27 AC 276 ms
12,588 KB
testcase_28 AC 291 ms
12,580 KB
testcase_29 AC 374 ms
12,644 KB
testcase_30 AC 398 ms
12,496 KB
testcase_31 AC 424 ms
12,660 KB
testcase_32 AC 121 ms
12,668 KB
testcase_33 AC 255 ms
12,668 KB
testcase_34 AC 274 ms
12,656 KB
testcase_35 AC 259 ms
12,680 KB
testcase_36 AC 256 ms
12,824 KB
testcase_37 AC 255 ms
12,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/880"

#include <iostream>
#include <numeric>

#include <cassert>
#include <vector>

#include <limits>
#include <iostream>
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

namespace suisen {

template <typename T, typename UpdateFunc, constraints_t<std::is_invocable<UpdateFunc>> = nullptr>
struct UpdateProxyObject {
    public:
        UpdateProxyObject(T &v, UpdateFunc update) : v(v), update(update) {}
        operator T() const { return v; }
        auto& operator++() && { ++v, update(); return *this; }
        auto& operator--() && { --v, update(); return *this; }
        auto& operator+=(const T &val) && { v += val, update(); return *this; }
        auto& operator-=(const T &val) && { v -= val, update(); return *this; }
        auto& operator*=(const T &val) && { v *= val, update(); return *this; }
        auto& operator/=(const T &val) && { v /= val, update(); return *this; }
        auto& operator%=(const T &val) && { v %= val, update(); return *this; }
        auto& operator =(const T &val) && { v  = val, update(); return *this; }
        auto& operator<<=(const T &val) && { v <<= val, update(); return *this; }
        auto& operator>>=(const T &val) && { v >>= val, update(); return *this; }
        template <typename F, constraints_t<std::is_invocable_r<T, F, T>> = nullptr>
        auto& apply(F f) && { v = f(v), update(); return *this; }
    private:
        T &v;
        UpdateFunc update;
};

} // namespace suisen

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)(), bool enable_beats = false>
    struct LazySegmentTree {
        using value_type = T;
        using operator_type = F;

        LazySegmentTree() : LazySegmentTree(0) {}
        LazySegmentTree(int n) : LazySegmentTree(std::vector<value_type>(n, e())) {}
        LazySegmentTree(const std::vector<value_type>& init) : n(init.size()), m(ceil_pow2(n)), lg(__builtin_ctz(m)), data(2 * m, e()), lazy(m, id()) {
            std::copy(init.begin(), init.end(), data.begin() + m);
            for (int k = m - 1; k > 0; --k) update(k);
        }

        void apply(int l, int r, const operator_type& f) {
            assert(0 <= l and l <= r and r <= n);
            push_to(l, r);
            for (int l2 = l + m, r2 = r + m; l2 < r2; l2 >>= 1, r2 >>= 1) {
                if (l2 & 1) all_apply(l2++, f);
                if (r2 & 1) all_apply(--r2, f);
            }
            update_from(l, r);
        }
        void apply(int p, const operator_type& f) {
            (*this)[p] = mapping(f, get(p));
        }

        value_type operator()(int l, int r) {
            assert(0 <= l and l <= r and r <= n);
            push_to(l, r);
            value_type res_l = e(), res_r = e();
            for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res_l = op(res_l, data[l++]);
                if (r & 1) res_r = op(data[--r], res_r);
            }
            return op(res_l, res_r);
        }

        value_type prod(int l, int r) { return (*this)(l, r); }
        value_type prefix_prod(int r) { return (*this)(0, r); }
        value_type suffix_prod(int l) { return (*this)(l, m); }
        value_type all_prod() const { return data[1]; }

        auto operator[](int p) {
            assert(0 <= p and p < n);
            push_to(p);
            return UpdateProxyObject{ data[p + m], [this, p] { update_from(p); } };
        }
        value_type get(int p) { return (*this)[p]; }
        void set(int p, value_type v) { (*this)[p] = v; }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, value_type>> = nullptr>
        int max_right(int l, Pred g) {
            assert(0 <= l && l <= n);
            assert(g(e()));
            if (l == n) return n;
            l += m;
            for (int i = lg; i >= 1; --i) push(l >> i);
            value_type sum = e();
            do {
                while ((l & 1) == 0) l >>= 1;
                if (not g(op(sum, data[l]))) {
                    while (l < m) {
                        push(l);
                        l = 2 * l;
                        if (g(op(sum, data[l]))) sum = op(sum, data[l++]);
                    }
                    return l - m;
                }
                sum = op(sum, data[l++]);
            } while ((l & -l) != l);
            return n;
        }
        template <bool(*f)(value_type)>
        int max_right(int l) { return max_right(l, f); }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, value_type>> = nullptr>
        int min_left(int r, Pred g) {
            assert(0 <= r && r <= n);
            assert(g(e()));
            if (r == 0) return 0;
            r += m;
            for (int i = lg; i >= 1; --i) push(r >> i);
            value_type sum = e();
            do {
                r--;
                while (r > 1 and (r & 1)) r >>= 1;
                if (not g(op(data[r], sum))) {
                    while (r < m) {
                        push(r);
                        r = 2 * r + 1;
                        if (g(op(data[r], sum))) sum = op(data[r--], sum);
                    }
                    return r + 1 - m;
                }
                sum = op(data[r], sum);
            } while ((r & -r) != r);
            return 0;
        }
        template <bool(*f)(value_type)>
        int min_left(int l) { return min_left(l, f); }
    private:
        int n, m, lg;
        std::vector<value_type> data;
        std::vector<operator_type> lazy;

        static constexpr int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }

        void all_apply(int k, const operator_type& f) {
            data[k] = mapping(f, data[k]);
            if (k < m) {
                lazy[k] = composition(f, lazy[k]);
                if constexpr (enable_beats) if (data[k].fail) push(k), update(k);
            }
        }
        void push(int k) {
            all_apply(2 * k, lazy[k]), all_apply(2 * k + 1, lazy[k]);
            lazy[k] = id();
        }
        void push_to(int p) {
            p += m;
            for (int i = lg; i >= 1; --i) push(p >> i);
        }
        void push_to(int l, int r) {
            l += m, r += m;
            int li = __builtin_ctz(l), ri = __builtin_ctz(r);
            for (int i = lg; i >= li + 1; --i) push(l >> i);
            for (int i = lg; i >= ri + 1; --i) push(r >> i);
        }
        void update(int k) {
            data[k] = op(data[2 * k], data[2 * k + 1]);
        }
        void update_from(int p) {
            p += m;
            for (int i = 1; i <= lg; ++i) update(p >> i);
        }
        void update_from(int l, int r) {
            l += m, r += m;
            int li = __builtin_ctz(l), ri = __builtin_ctz(r);
            for (int i = li + 1; i <= lg; ++i) update(l >> i);
            for (int i = ri + 1; i <= lg; ++i) update(r >> i);
        }
    };
}

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    using SegmentTreeBeats = LazySegmentTree<T, op, e, F, mapping, composition, id, /* enable_beats = */ true>;
} // namespace suisen

constexpr int inf = 2000000000;

int sat_lcm(int x, int y) {
    if (x == inf or y == inf) return inf;
    return std::min<long long>(inf, 1LL * (x / std::gcd(x, y)) * y);
}

struct S {
    long long sum_v;
    int max_v;
    int lcm_v;
    int siz;
    bool fail = false;

    S(long long sum_v, int max_v, int lcm_v, int siz) : sum_v(sum_v), max_v(max_v), lcm_v(lcm_v), siz(siz) {}
    S(int v) : sum_v(v), max_v(v), lcm_v(v), siz(1) {}
    S() = default;
};

struct F {
    int upd_v = 0;
    int gcd_v = 0;

    F(int upd_v = 0, int gcd_v = 0) : upd_v(upd_v), gcd_v(gcd_v) {}

    static F upd_query(int upd_v) {
        return F { upd_v, 0 };
    }
    static F gcd_query(int gcd_v) {
        return F { 0, gcd_v };
    }
};

S op(S x, S y) {
    return S { x.sum_v + y.sum_v, std::max(x.max_v, y.max_v), sat_lcm(x.lcm_v, y.lcm_v), x.siz + y.siz };
}
S e() {
    return S { 0LL, 0, 1, 0 };
}

S mapping(F f, S x) {
    if (x.fail) return x;
    if (x.sum_v == 1LL * x.max_v * x.siz and f.gcd_v) {
        f = F::upd_query(std::gcd(x.max_v, f.gcd_v));
    }
    if (f.upd_v) return S { (long long) f.upd_v * x.siz, f.upd_v, f.upd_v, x.siz };
    if (f.gcd_v) {
        if (x.siz == 1) {
            return S { std::gcd(x.max_v, f.gcd_v) };
        } else if (x.lcm_v == inf or f.gcd_v % x.lcm_v) {
            x.fail = true;
        }
    }
    return x;
}

F composition(F f, F g) {
    if (f.upd_v) return f;
    if (g.upd_v) return F::upd_query(std::gcd(g.upd_v, f.gcd_v));
    return F::gcd_query(std::gcd(f.gcd_v, g.gcd_v));
}
F id() {
    return F::gcd_query(0);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::vector<S> init(n);
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        init[i] = S{v};
    }

    suisen::SegmentTreeBeats<S, op, e, F, mapping, composition, id> seg(init);
    while (q --> 0) {
        int qt;
        std::cin >> qt;
        if (qt == 1) {
            int l, r, x;
            std::cin >> l >> r >> x;
            --l;
            seg.apply(l, r, F::upd_query(x));
        } else if (qt == 2) {
            int l, r, x;
            std::cin >> l >> r >> x;
            --l;
            seg.apply(l, r, F::gcd_query(x));
        } else if (qt == 3) {
            int l, r;
            std::cin >> l >> r;
            --l;
            std::cout << seg.prod(l, r).max_v << '\n';
        } else {
            int l, r;
            std::cin >> l >> r;
            --l;
            std::cout << seg.prod(l, r).sum_v << '\n';
        }
    }

    return 0;
}
0