Dynamic Range Minimum Queries

n, q = map(int, input().split())
a = list(map(int, input().split()))

t = [1 << 62] * (2 * n)

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

o = []

for _ in range(q):
    c, x, y = map(int, input().split())
    if c == 1:
        k = x - 1 + n
        t[k] = y
        k >>= 1
        while k:
            t[k] = min(t[2 * k], t[2 * k + 1])
            k >>= 1
    else:
        l = x - 1 + n
        r = y - 1 + n
        m = 1 << 62
        while l <= r:
            if l & 1:
                m = min(m, t[l]); l += 1
            if not r & 1:
                m = min(m, t[r]); r -= 1
            l >>= 1; r >>= 1
        o.append(m)
        
print('\n'.join(map(str, o)))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED