library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub sash2104/library

:heavy_check_mark: セグメント木 (一点更新・区間最小)
(test/aoj/DSL_2_A.test.cpp)

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"
// @title セグメント木 (一点更新・区間最小)

#include "../../monoid/min.hpp"
#include "../../datastructure/segment-tree.hpp"

#include <iostream>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  SegmentTree<monoid::min<int>> st(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y;
    if (c == 0) st.update(x, y);
    else cout << st.query(x, y+1) << endl;
  }
}
#line 1 "test/aoj/DSL_2_A.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"
// @title セグメント木 (一点更新・区間最小)

#line 1 "monoid/min.hpp"


#include <algorithm>
#include <limits>

namespace monoid {
template <class T>
struct min {
  typedef T value_t;
  T identity() const { return std::numeric_limits<T>::max();}
  T merge(T a, T b) const { return std::min(a, b); }
};
} // namespace monoid


#line 1 "datastructure/segment-tree.hpp"


/**
 * @title セグメント木 (一点更新、区間取得)
 * 
 */
#include <cassert>
#include <vector>

template <class Monoid>
struct SegmentTree {
  typedef typename Monoid::value_t value_t;
  const Monoid monoid;
  int n; // n_以上の最小の2冪
  std::vector<value_t> data;
  SegmentTree(int n_): monoid() {
    n = 1;
    while (n < n_) n *= 2;
    data.assign(2*n-1, monoid.identity());
  }

  // k番目の値(0-indexed)をaに変更
  void update(int k, int a) { // 0-indexed
    assert(0 <= k && k < n);
    // 葉の節点
    data[k+n-1] = a;
    // 登りながら更新
    for (k = (k+n)/2; k > 0; k /= 2) {  // 1-indexed
      data[k-1] = monoid.merge(data[2*k-1], data[2*k]);
    }
  }

  value_t query(int l, int r) {  // 0-indexed, [l, r)
    assert(0 <= l && l <= r && r <= n);
    value_t vl = monoid.identity(), vr = monoid.identity();
    for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-indexed
      if (l & 1) vl = monoid.merge(vl, data[(l++)-1]);
      if (r & 1) vr = monoid.merge(data[(--r)-1],vr);
    }
    return monoid.merge(vl, vr);
  }

  value_t operator[](const int &k) {
    return query(k, k + 1);
  }
};


#line 6 "test/aoj/DSL_2_A.test.cpp"

#include <iostream>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  SegmentTree<monoid::min<int>> st(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y;
    if (c == 0) st.update(x, y);
    else cout << st.query(x, y+1) << endl;
  }
}
Back to top page