Dynamic Range Minimum Queries

n, q = [int(x) for x in input().split()]
N = 1 << (n-1).bit_length()
# print(N)
array = [int(x) for x in input().split()]
minimums = [10**10 for _ in range(2*N)]
for i in range(n):
    minimums[N+i] = array[i]


def BuildSparseTree():
    for i in range(N-1, 0, -1):
        minimums[i] = min(minimums[i*2], minimums[i*2+1])

BuildSparseTree()

output = []
for i in range(q):
    action, k, u = [int(x) for x in input().split()]
    if action == 1: 
        pos = N + k - 1
        minimums[pos] = u
        pos //=2
        while pos > 0:
            minimums[pos] = min(minimums[pos*2], minimums[pos*2+1])
            pos //=  2
    else: 
        l = N + k - 1
        r = N + u
        s = 10 ** 10
        while l < r:
            if l & 1: 
                s = min(s, minimums[l])
                l += 1
            if r&1: 
                r -= 1
                s = min(s, minimums[r])
            l //= 2
            r //= 2
        output.append(str(s))

print("\n".join(output))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED