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_size = square_n
if square_n * square_n < n:
    min_array_size += 1

min_array = [0 for _ in range(min_array_size)]

#preprocess
for i in range(min_array_size):
    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): #before 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: #after 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: ACCEPTED