Dynamic Range Minimum Queries

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1

    a = data[idx:idx+n]
    a = list(map(int, a))
    idx += n

    size = n
    INF = float('inf')
    seg = [INF] * (2 * size)

    # build
    for i in range(size):
        seg[size + i] = a[i]
    for i in range(size - 1, 0, -1):
        seg[i] = seg[2*i] if seg[2*i] < seg[2*i+1] else seg[2*i+1]

    def update(pos, val):
        pos += size
        seg[pos] = val
        pos >>= 1
        while pos >= 1:
            left = seg[2*pos]
            right = seg[2*pos+1]
            seg[pos] = left if left < right else right
            pos >>= 1

    def query(l, r):  # inclusive, 0-indexed
        l += size
        r += size + 1
        res = INF
        while l < r:
            if l & 1:
                if seg[l] < res: res = seg[l]
                l += 1
            if r & 1:
                r -= 1
                if seg[r] < res: res = seg[r]
            l >>= 1
            r >>= 1
        return res

    out = []
    for _ in range(q):
        t = int(data[idx]); idx += 1
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        if t == 1:
            update(x - 1, y)
        else:
            out.append(query(x - 1, y - 1))

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

main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED