Dynamic Range Minimum Queries

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

square_n = int(round(n**(1/2), 0))
min_array = [0 for _ in range(square_n)]

#preprocess
for i in range(square_n):
    reduces_array = array[i*square_n:(i+1)*square_n]
    min_array[i] = min(reduces_array)

def query(a, b):
    mini = float('inf')
    while (a < b) and (a % square_n != 0) and (a != 0): #first block
        mini = min(array[a], mini)
        a += 1

    while (a + square_n - 1 <= b): #overlapped blocks
        mini = min(min_array[a//square_n], mini)
        a += square_n

    while (a <= b): #last block
        mini = min(array[a], mini)
        a += 1

    return mini

solution = []
for _ in range(q):
    indic, k, u = [int(x) for x in input().split()]
    if indic == 1:
        array[k-1] = u
        index = (k-1) // square_n
        reduces_array = array[index*square_n:(index+1)*square_n]
        min_array[index] = min(reduces_array)
    else:
        solution.append(query(k-1,u-1))

for elt in solution:
    print(elt)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 35, in <module>
    min_ar...