:heavy_check_mark: test/AOJ/DSL_2_D.test.cpp

Depends on

Code

#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D"
#include <bits/stdc++.h>

#include "library/algebra/lazy/SetMin.hpp"
#include "library/segtree/DualSegmentTree.hpp"

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

    int n, q;
    std::cin >> n >> q;
    DualSegmentTree<LazySetMin<int>> seg(std::vector<int>(n, (1LL << 31) - 1));
    while (q--) {
        int t;
        std::cin >> t;
        if (t) {
            int i;
            std::cin >> i;
            std::cout << seg[i] << "\n";
        } else {
            int l, r, x;
            std::cin >> l >> r >> x;
            r++;
            seg.apply(l, r, x);
        }
    }
}
#line 1 "test/AOJ/DSL_2_D.test.cpp"
#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D"
#include <bits/stdc++.h>

#line 1 "library/algebra/monoid/Min.hpp"
template <typename X> struct MonoidMin {
    using value_type = X;
    static constexpr X op(const X &x, const X &y) noexcept {
        return std::min(x, y);
    }
    static constexpr void Rchop(X &x, const X &y) {
        if (x > y)
            x = y;
    }
    static constexpr void Lchop(const X &x, X &y) {
        if (y > x)
            y = x;
    }
    static constexpr X unit() { return std::numeric_limits<X>::max() / 2; }
    static constexpr bool commute = true;
};
#line 2 "library/algebra/monoid/Set.hpp"
// 合成の順番は関数と一緒だよ
template <typename X> struct MonoidSet {
    using O = std::optional<X>;
    using value_type = O;
    static constexpr O op(const O &x, const O &y) noexcept {
        return (x.has_value() ? x : y);
    }
    static constexpr void Rchop(O &x, const O &y) {
        if (!x)
            x = y;
    }
    static constexpr void Lchop(const O &x, O &y) {
        if (x)
            y = x;
    }
    static constexpr O unit() noexcept { return std::nullopt; }
    static constexpr bool commute = false;
};
#line 4 "library/algebra/lazy/SetMin.hpp"
template <typename X> struct LazySetMin {
    using MX = MonoidMin<X>;
    using MF = MonoidSet<X>;
    using F = typename MF::value_type;
    static constexpr X mapping(const F &f, const X &x) { return f.value_or(x); }
};
#line 1 "library/segtree/DualSegmentTree.hpp"
template <typename Lazy> class DualSegmentTree {
    using MX = typename Lazy::MX;
    using MF = typename Lazy::MF;
    using X = typename MX::value_type;
    using F = typename MF::value_type;
    int n, log, size;
    std::vector<X> dat;
    std::vector<F> laz;

    void point_apply(int k, const F &f) {
        if (k < size)
            MF::Lchop(f, laz[k]);
        else
            dat[k - size] = Lazy::mapping(f, dat[k - size]);
    }
    void push(int k) {
        point_apply(2 * k, laz[k]);
        point_apply(2 * k + 1, laz[k]);
        laz[k] = MF::unit();
    }
    void thrust(int k) {
        for (int i = log; i; i--)
            push(k >> i);
    }

  public:
    DualSegmentTree() : DualSegmentTree(0) {}
    DualSegmentTree(int n) : DualSegmentTree(std::vector<X>(n, MX::unit())) {}
    DualSegmentTree(const std::vector<X> &v) : n(v.size()), dat(v) {
        for (log = 1; (1 << log) < n; log++) {
        }
        size = 1 << log;
        laz.assign(size, MF::unit());
    }

    void set(int p, X x) {
        assert(0 <= p and p < n);
        thrust(p + size);
        dat[p] = x;
    }

    X operator[](int p) {
        assert(0 <= p and p < n);
        thrust(p + size);
        return dat[p];
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r)
            return;
        thrust(l += size);
        thrust(r += size - 1);
        for (int L = l, R = r + 1; L < R; L >>= 1, R >>= 1) {
            if (L & 1)
                point_apply(L++, f);
            if (R & 1)
                point_apply(--R, f);
        }
    }
};
#line 7 "test/AOJ/DSL_2_D.test.cpp"

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

    int n, q;
    std::cin >> n >> q;
    DualSegmentTree<LazySetMin<int>> seg(std::vector<int>(n, (1LL << 31) - 1));
    while (q--) {
        int t;
        std::cin >> t;
        if (t) {
            int i;
            std::cin >> i;
            std::cout << seg[i] << "\n";
        } else {
            int l, r, x;
            std::cin >> l >> r >> x;
            r++;
            seg.apply(l, r, x);
        }
    }
}
Back to top page