Dynamic Range Minimum Queries

import math

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

def calculateMins():
    minimums = {}
    for i in range(n):
        for j in range(i, n):
            if i != j and math.log2(j-i + 1) % 1 == 0:
                minimums.update({str((i+1, j+1)) : min(array[i:j+1])}) 
    # print(minimums)
    return minimums

minimums = calculateMins()
output = []

for i in range(q):
    action, k, u = [int(x) for x in input().split()]
    if action == 1: 
        array[k - 1] = u
        minimums = calculateMins()
    else: 
        if k != u:
            start = int(math.log2(u))
            minPower = 2 ** start  
            while minPower > u - k + 1: 
                start -= 1   
                minPower = 2 ** start

            # print(minPower, str((k, k + minPower - 1)), str((u - minPower + 1, u)))
            output.append(str(min(minimums[str((k, k + minPower - 1))], minimums[str((u - minPower + 1, u))])))
        else: output.append(str(array[u - 1]))

print("\n".join(output))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED