test/aoj/dsl_2_a.test.cpp

View this file on GitHub
Last update: 2022-12-24 07:22:57+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

Depends on

src/structure/segment_tree.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../../src/structure/segment_tree.hpp"

int main() {
  int n, q;
  cin >> n >> q;
  long long INF = (1L << 31) - 1;
  SegmentTree<long long> st(
      n, [](long long a, long long b) { return min(a, b); }, INF);
  for (int i = 0; i < q; ++i) {
    int com, x, y;
    cin >> com >> x >> y;
    if (com == 0) {
      st.update(x, y);
    } else {
      cout << st.query(x, y + 1) << endl;
    }
  }
  return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/structure/segment_tree.hpp"

#line 4 "src/structure/segment_tree.hpp"
using namespace std;

template <typename Monoid> struct SegmentTree {
private:
  using BinaryOperation = function<Monoid(Monoid, Monoid)>;
  const BinaryOperation binary_operation;
  const Monoid identity_element;

  int leaf_n;
  vector<Monoid> data;

public:
  SegmentTree(int n, const BinaryOperation bo, const Monoid ie)
      : binary_operation(bo), identity_element(ie) {
    leaf_n = 1;
    while (leaf_n < n) {
      leaf_n *= 2;
    }
    int data_n = leaf_n * 2;
    data.assign(data_n, identity_element);
  }

  // i is 0-indexed.
  void set(int i, const Monoid &v) { data[i + leaf_n] = v; }

  void build() {
    for (int i = leaf_n - 1; i > 0; --i) {
      data[i] = binary_operation(data[2 * i], data[2 * i + 1]);
    }
  }

  // i is 0-indexed.
  void update(int i, const Monoid &v) {
    i += leaf_n;
    data[i] = v;
    while (i >>= 1) {
      data[i] = binary_operation(data[2 * i], data[2 * i + 1]);
    }
  }

  // [i, j), i and j are 0-indexed
  Monoid query(int i, int j) {
    Monoid v_left = identity_element, v_right = identity_element;
    for (int left = i + leaf_n, right = j + leaf_n; left < right;
         left >>= 1, right >>= 1) {
      if (left & 1) {
        v_left = binary_operation(v_left, data[left++]);
      }
      if (right & 1) {
        v_right = binary_operation(data[--right], v_right);
      }
    }
    return binary_operation(v_left, v_right);
  }

  // i is 0-indexed.
  Monoid operator[](int i) const { return data[i + leaf_n]; }
};
#line 8 "test/aoj/dsl_2_a.test.cpp"

int main() {
  int n, q;
  cin >> n >> q;
  long long INF = (1L << 31) - 1;
  SegmentTree<long long> st(
      n, [](long long a, long long b) { return min(a, b); }, INF);
  for (int i = 0; i < q; ++i) {
    int com, x, y;
    cin >> com >> x >> y;
    if (com == 0) {
      st.update(x, y);
    } else {
      cout << st.query(x, y + 1) << endl;
    }
  }
  return 0;
}