Dynamic Range Minimum Queries

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

#define PRINT_ARR(arr, n)                                                      \
  do {                                                                         \
    for (int i = 0; i < n; i++) {                                              \
      cout << arr[i] << " ";                                                   \
    }                                                                          \
    cout << "\n";                                                              \
  } while (0)
#define DEF_VAL LONG_LONG_MAX

typedef long long ll;

int max_exp(int a, int b) {
  int diff = b - a + 1;
  int exp;
  for (exp = 0; diff >>= 1; exp++)
    ;
  return exp;
}
void s_update(int k, ll value, ll *arr, int size) {
  k += size / 2 - 1;
  arr[k] = value;
  for (k /= 2; k >= 1; k /= 2) {
    arr[k] = min(arr[2 * k], arr[2 * k + 1]);
  }
}

ll s_min(int a, int b, ll *arr, int size) {
  a += size / 2 - 1;
  b += size / 2 - 1;
  ll s = arr[0];
  while (a <= b) {
    if (a % 2 == 1)
      s = min(s, arr[a++]);
    if (b % 2 == 0)
      s = min(s, arr[b--]);
    a /= 2;
    b /= 2;
  }
  return s;
}

void s_init(ll *arr, int size, int nof_elem) {
  int t;
  for (int i = 1; i <= nof_elem; i++) {
    cin >> t;
    s_update(i, t, arr, size);
  }
}

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

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

  int temp = max_exp(0, n - 1);
  temp = 1 << temp;
  if (temp < n) {
    temp <<= 1;
  }
  int size = temp * 2;
  ll arr[size];
  for (int i = 0; i < size; i++) {
    arr[i] = DEF_VAL;
  }

  s_init(arr, size, n);

  int c, l, r;
  for (int i = 0; i < q; i++) {
    cin >> c >> l >> r;
    if (c == 1) {
      s_update(l, r, arr, size);
    } else {
      cout << s_min(l, r, arr, size) << endl;
    }
  }

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED