Dynamic Range Minimum Queries

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define BR "\n"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pi;

struct MinSegTree {
  vi t;
  int n;

  MinSegTree(int a[], int n) : t(vi(4 * n + 1)), n(n) { build(a, 1, 0, n - 1); }

  int minimum(int l, int r) { return minimumrec(1, 0, n - 1, l, r); }
  void update(int pos, int v) { return updaterec(1, 0, n - 1, pos, v); }

 private:
  void updaterec(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
      t[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
        updaterec(v * 2, tl, tm, pos, new_val);
      else
        updaterec(v * 2 + 1, tm + 1, tr, pos, new_val);
      t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
  }

  void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
  }

  int minimumrec(int v, int tl, int tr, int l, int r) {
    if (l > r) {
      return INT_MAX;
    }
    if (l == tl && r == tr) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(minimumrec(v * 2, tl, tm, l, min(r, tm)),
               minimumrec(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
  }
};

int main() {
  // uncomment if io is a bottleneck
  // ios::sync_with_stdio(0);
  // cin.tie(0);

  // uncomment to read cin from a file
  // freopen("dynamic-range-minimum-queries.txt", "r", stdin);

  int n, q;
  cin >> n >> q;

  int a[n];
  REP(i, 0, n) { cin >> a[i]; }

  MinSegTree t(a, n);

  REP(i, 0, q) {
    int op;
    int c, d;
    cin >> op >> c >> d;

    if (op == 1) {
      t.update(c - 1, d);
    } else if (op == 2) {
      cout << t.minimum(c - 1, d - 1) << BR;
    }
  }

  return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED