Test/DataStructure/DynamicSegmentTree_RMQ.test.cpp

View this file on GitHub
Last update: 2025-12-20 16:12:20+00:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

Depends on

Code

#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A"

#include <iostream>


// begin:tag includes

#include "./../../Library/DataStructure/DynamicSegmentTree.hpp"

// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

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

  auto op = [](ll a, ll b) { return std::min(a, b); };
  using M = mtd::Monoid<ll, (1LL << 31) - 1, decltype(op)>;
  auto segtree = mtd::DynamicSegmentTree<M>();

  for (int _ = 0; _ < q; ++_) {
    int k, x, y;
    std::cin >> k >> x >> y;
    if (k == 0) {
      segtree.update(x, y);
    } else {
      std::cout << segtree.query(x, y) << std::endl;
    }
  }
}

#line 1 "Test/DataStructure/DynamicSegmentTree_RMQ.test.cpp"
#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A"

#include <iostream>


// begin:tag includes

#line 2 "Library/DataStructure/DynamicSegmentTree.hpp"

#include <memory>

#include <ostream>

#include <utility>

#include <vector>


#line 2 "Library/Algebraic/Monoid.hpp"

#line 4 "Library/Algebraic/Monoid.hpp"

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op    // binary operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Monoid {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;

    S m_val;
    constexpr Monoid(S val) : m_val(val) {}
    constexpr Monoid() : Monoid(element) {}
    constexpr Monoid binaryOperation(const Monoid& m2) const {
      return op()(m_val, m2.m_val);
    }
    friend std::ostream& operator<<(std::ostream& os,
                                    const Monoid<S, element, op>& m) {
      return os << m.m_val;
    }
  };

  namespace __detail {
    template <typename T, template <typename, auto, typename> typename S>
    concept is_monoid_specialization_of = requires {
      typename std::enable_if_t<std::is_same_v<
          T, S<typename T::value_type, T::_element, typename T::op_type>>>;
    };
  }  // namespace __detail

  template <typename M>
  concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;

}  // namespace mtd
#line 9 "Library/DataStructure/DynamicSegmentTree.hpp"

namespace mtd {
  template <monoid Monoid, int size = static_cast<int>(1e9 + 1)>
  class DynamicSegmentTree {
  private:
    using S = decltype(Monoid().m_val);

    struct Node {
      Monoid val;
      std::unique_ptr<Node> left;
      std::unique_ptr<Node> right;
      Node() : val(Monoid()), left(nullptr), right(nullptr) {}
      explicit Node(const Monoid& v) : val(v), left(nullptr), right(nullptr) {}
    };

    std::unique_ptr<Node> m_root;

    template <class Lambda>
    constexpr void _update_op(std::unique_ptr<Node>& node, int l, int r, int pos,
                               Monoid&& val, const Lambda& op) {
      if (!node) node = std::make_unique<Node>();
      if (r - l == 1) {
        node->val = op(node->val, std::forward<Monoid>(val));
        return;
      }
      int mid = l + (r - l) / 2;
      if (pos < mid) {
        _update_op(node->left, l, mid, pos, std::forward<Monoid>(val), op);
      } else {
        _update_op(node->right, mid, r, pos, std::forward<Monoid>(val), op);
      }
      Monoid left_val = node->left ? node->left->val : Monoid();
      Monoid right_val = node->right ? node->right->val : Monoid();
      node->val = left_val.binaryOperation(right_val);
    }

    constexpr Monoid _query(const std::unique_ptr<Node>& node, int l, int r,
                            int ql, int qr) const {
      if (!node || r <= ql || qr <= l) return Monoid();
      if (ql <= l && r <= qr) return node->val;
      int mid = l + (r - l) / 2;
      return _query(node->left, l, mid, ql, qr)
          .binaryOperation(_query(node->right, mid, r, ql, qr));
    }

  public:
    constexpr DynamicSegmentTree() : m_root(nullptr) {}

    template <class Lambda>
    constexpr auto update_op(int pos, Monoid&& val, const Lambda& op) {
      return _update_op(m_root, 0, size, pos, std::forward<Monoid>(val), op);
    }

    constexpr auto update(int pos, Monoid&& val) {
      return update_op(pos, std::forward<Monoid>(val),
                       [](const Monoid&, const Monoid& m2) { return m2; });
    }

    constexpr auto add(int pos, Monoid&& val) {
      return update_op(pos, std::forward<Monoid>(val),
                       [](const Monoid& m1, const Monoid& m2) {
                         return Monoid(m1.m_val + m2.m_val);
                       });
    }

    constexpr auto query(int l, int r) const {
      if (l > r) return Monoid().m_val;
      return _query(m_root, 0, size, l, r + 1).m_val;
    }

    constexpr auto query_all() const {
      return m_root ? m_root->val.m_val : Monoid().m_val;
    }
  };

}  // namespace mtd

#line 8 "Test/DataStructure/DynamicSegmentTree_RMQ.test.cpp"
// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

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

  auto op = [](ll a, ll b) { return std::min(a, b); };
  using M = mtd::Monoid<ll, (1LL << 31) - 1, decltype(op)>;
  auto segtree = mtd::DynamicSegmentTree<M>();

  for (int _ = 0; _ < q; ++_) {
    int k, x, y;
    std::cin >> k >> x >> y;
    if (k == 0) {
      segtree.update(x, y);
    } else {
      std::cout << segtree.query(x, y) << std::endl;
    }
  }
}