Dynamic Range Minimum Queries

''''

'''

import sys 
import math
input_d = sys.stdin.read().split()

n = int(input_d[0])
q = int(input_d[1])

vals = [int(i) for i in input_d[2:n+2]]
queries = []
i = n+2
for k in range(i,len(input_d),3):
    queries.append([int(i) for i in input_d[k:k+3]])

nn = 2**(math.ceil(math.log2(n))) if n>0 else 1  #next power of two to handle cases where $n$ is not a power of two

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

#gotta handle if n is not a power of two

#first original elements
for i in range(n):
    tree[nn+i] = vals[i]

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



def update(k,x):
    k += nn 
    tree[k]=x #replace value
    k//=2
    while(k>=1):
        tree[k] = min(tree[2*k],tree[2*k+1])
        k//=2
def getmin(a,b):
    a+=nn
    b+=nn 
    minres = float('inf')

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


for query in queries:
    if query[0] == 1:
        #update
        update(query[1]-1,query[2])
    elif query[0]==2:
        getmin(query[1]-1,query[2]-1)



    

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED