Dynamic Range Minimum Queries

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    q = int(input_data[1])

    tree = [0] * (2 * n)

    for i in range(n):
        tree[n + i] = int(input_data[2 + i])

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

    idx = 2 + n
    out = []

    for _ in range(q):
        type_q = input_data[idx]
        if type_q == '1':
            k = int(input_data[idx + 1]) - 1 + n
            u = int(input_data[idx + 2])
            tree[k] = u
            k //= 2
            while k >= 1:
                tree[k] = min(tree[2 * k], tree[2 * k + 1])
                k //= 2
        else:
            l = int(input_data[idx + 1]) - 1 + n
            r = int(input_data[idx + 2]) - 1 + n
            res = float('inf')
            while l <= r:
                if l % 2 == 1:
                    if tree[l] < res:
                        res = tree[l]
                    l += 1
                if r % 2 == 0:
                    if tree[r] < res:
                        res = tree[r]
                    r -= 1
                l //= 2
                r //= 2
            out.append(str(res))
        idx += 3

    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED