Dynamic Range Minimum Queries

def findMin(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        if arr[lo] < arr[hi]:
            return arr[lo]
        mid = (lo + hi) // 2
        if arr[mid] > arr[hi]:
            lo = mid + 1
        else:
            hi = mid
    return arr[lo]


def rangeQuery(n, q, arr, commands):
    result = []
    for command in commands:
        if command[0] == 1:
            arr[command[1] - 1] = command[2]
        else:
            start, end = command[1] - 1, command[2] - 1
            # min_num = float('inf')
            # for i in range(start, end + 1):
            #     if arr[i] < min_num:
            #         min_num = arr[i]
            min_num = findMin(sorted(arr[start:end+1]))
            result.append(min_num)
            # print(min_num)
    return result

def main():
    # n, q = 8, 4
    # arr = [3, 2, 4, 5, 1, 1, 5, 3]
    # commands = [[2, 1, 4], [2, 5, 6], [1, 2, 3], [2, 1, 4]]
    # result = rangeQuery(n, q, arr, commands)
    # print(*result, sep='\n')


    n, q = map(int, input().split())
    arr = list(map(int, input().split()))
    commands = [list(map(int, input().split())) for _ in range(q)]
    result = rangeQuery(n, q, arr, commands)
    print(*result, sep='\n')



if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED