test/segmentTree/rangeMin.aoj_DSL_2_A.test.cpp

• View this file on GitHub
• Last update: 2022-07-06 23:37:31+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

Depends on

• Range Minimum Query (segmentTree/rangeMin.hpp)

Code

#define PROBLEM \
  "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"

#include "../../segmentTree/rangeMin.hpp"
#include <iostream>

int main() {
  int n, q, com, x, y;
  cin >> n >> q;
  rangeMin st;
  st.init(n);
  for (int i = 0; i < n; i++) {
    st.update(i, INT32_MAX);
  }
  for (int i = 0; i < q; i++) {
    cin >> com >> x >> y;
    if (com == 0) {
      st.update(x, y);
    } else {
      cout << st.query(x, y + 1) << endl;
    }
  }
}

#line 1 "test/segmentTree/rangeMin.aoj_DSL_2_A.test.cpp"
#define PROBLEM \
  "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"

#line 2 "segmentTree/rangeMin.hpp"
#include<vector>
#include<algorithm>
using namespace std;
class rangeMin {
 public:
  int size_ = 1;
  vector<long long> dat;

  void init(int sz) {
    while (size_ <= sz) size_ *= 2;
    dat.resize(size_ * 2, 1LL << 60);
  }
  void update(int pos, long long x) {
    pos += size_;
    dat[pos] = x;
    while (pos /= 2) {
      dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
    }
  }
  long long query_(int l, int r, int a, int b, int u) {
    if (l <= a && b <= r) return dat[u];
    if (r <= a || b <= l) return 1LL << 60;
    int mid = (a + b) / 2;
    long long v1 = query_(l, r, a, mid, u * 2);
    long long v2 = query_(l, r, mid, b, u * 2 + 1);
    return min(v1, v2);
  }
  long long query(int l, int r) { return query_(l, r, 0, size_, 1); }
};
#line 5 "test/segmentTree/rangeMin.aoj_DSL_2_A.test.cpp"
#include <iostream>

int main() {
  int n, q, com, x, y;
  cin >> n >> q;
  rangeMin st;
  st.init(n);
  for (int i = 0; i < n; i++) {
    st.update(i, INT32_MAX);
  }
  for (int i = 0; i < q; i++) {
    cin >> com >> x >> y;
    if (com == 0) {
      st.update(x, y);
    } else {
      cout << st.query(x, y + 1) << endl;
    }
  }
}

Back to top page