Dynamic Range Minimum Queries

n, q = [int(x) for x in input().split()]
values = [int(x) for x in input().split()]
queries = []

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

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

def compute_minimum(a, b):
    a += n
    b += n
    minimum = float('inf')
    while a <= b:
        if a%2 == 1:
            minimum = min(minimum, min_queries[a])
            a += 1
        if b%2 == 0:
            minimum = min(minimum, min_queries[b])
            b -= 1
        a //= 2
        b //= 2
    
    queries.append(minimum)

for _ in range(q):
    query = [int(x) for x in input().split()]
    a = query[1]-1
    if query[0] == 1:
        update(a, query[2])
    else:
        b = query[2]-1
        compute_minimum(a, b)

for i in range(len(queries)):
    print(queries[i])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED