Dynamic Range Minimum Queries

import math

def main():
    n, q = [int(x) for x in input().split()]
    values = [int(x) for x in input().split()]

    N = 1
    while N < n:
        N *= 2

    tree = [float('inf')] * N * 2

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

    def update(k, x):
        k += N
        tree[k] = x
        k //= 2
        while k >= 1:
            tree[k] = min(tree[k * 2], tree[k * 2 + 1])
            k //= 2

    def query(a, b):
        a += N
        b += N
        s = float('inf')

        while a <= b:
            if a % 2 == 1:
                s = min(s, tree[a])
                a += 1
            if b % 2 == 0:
                s = min(s, tree[b])
                b -= 1
            a //= 2
            b //= 2
        return s

    for _ in range(q):
        action = [int(x) for x in input().split()]

        if action[0] == 1:
            update(action[1] - 1, action[2])
        else:
            print(query(action[1] - 1, action[2] - 1))

main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED