Dynamic Range Minimum Queries

n, q = map(int, input().split())
arr = list(map(int, input().split()))

tree = [0] * (2 * n)

for i in range(n):
    tree[n + i] = arr[i]

for i in range(n - 1, 0, -1):
    tree[i] = min(tree[2 * i], tree[2 * i + 1])


def update(k, u):
    k += n
    tree[k] = u
    k //= 2
    while k >= 1:
        tree[k] = min(tree[2 * k], tree[2 * k + 1])
        k //= 2


def query(a, b):
    a += n
    b += n
    result = float('inf')
    while a <= b:
        if a % 2 == 1:
            result = min(result, tree[a])
            a += 1
        if b % 2 == 0:
            result = min(result, tree[b])
            b -= 1
        a //= 2
        b //= 2
    return result


for _ in range(q):
    line = list(map(int, input().split()))
    if line[0] == 1:
        k, u = line[1] - 1, line[2]
        update(k, u)
    else:
        a, b = line[1] - 1, line[2] - 1
        print(query(a, b))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED