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(1, n + 1):
#     for j in range(i, n + 1):
#         print(i, j)
#         k = i + N 
#         u = j + N
#         s = min(minimums[k], minimums[u])
#         u //= 2
#         k //= 2
#         while k < u:
#             if k % 2 == 1: 
#                 s = min(s, minimums[k])
#                 k += 1
#             if u % 2 == 0: 
#                 s = min(s, minimums[u])
#                 u -= 1
#             k = k // 2
#             u = u // 2
#         print(s)

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

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

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED