Segment Tree

const int64_t INF = (int64_t)1e18 + 5;

struct SegmTree {
  int n;
  vector<int64_t> tree;

  SegmTree(int n_) : n(n_), tree(2 * n, INF) {}

  void Update(int l, int r, int64_t val) {
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) tree[l] = min(tree[l], val), ++l;
      if (r & 1) --r, tree[r] = min(tree[r], val);
    }
  }

  int64_t Query(int pos) {
    int64_t ans = INF;
    for (pos += n; pos; pos /= 2)
      ans = min(ans, tree[pos]);
    return ans;
  }
};