Problem:

Range Minimum Query (RMQ)

Write a program which manipulates a sequence A = {a0, a1, . . .  , an-1} with the following operations:

find(s, t): report the minimum element in as, as+1, . . . ,at.

update(i, x): change ai to x.

Note that the initial values of ai (i = 0, 1, . . .  , n&minus;1) are  231-1.

Input

n q
com0 x0 y0
com1 x1 y1
...
comq&minus;1 xq&minus;1 yq&minus;1

In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, q queries are given where com represents the type of queries. '0' denotes update(xi, yi) and '1' denotes find(xi, yi).

Output

For each find operation, print the minimum element.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

If comi is 0, then 0 ≤ xi < n, 0 ≤ yi < 231-1.

If comi is 1, then 0 ≤ xi < n, 0 ≤ yi < n.

Sample Input 1

3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

Sample Output 1

1
2

Sample Input 2

1 3
1 0 0
0 0 5
1 0 0

Sample Output 2

2147483647
5



Sample input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2


Sample output:
1
2

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# !/bin/python

import math
import itertools

INITER = 2**32-1


class sqrt_deco(object):
    """
    >>> data = sqrt_deco(5, min)
    >>> data.update(1, 2)
    >>> data.raw_data
    [INF, 2, INF]
    >>> data.query(0, 2)
    2
    """
    def __init__(self, len_element: int, op=min):
        self.len_element = len_element
        self.op = op
        self.raw_data = list(itertools.repeat(INITER, self.len_element))
        
        self.deco_data = self.init_operation(self.raw_data)
    
    def init_operation(self, raw_data):
        index_size = int(math.ceil(math.sqrt(self.len_element)))
        
        index = [i * index_size for i in range(index_size)]
        _ = index.pop()
        
        init_data = [self.op(raw_data[s: s+index_size]) for s in index]
        
        return init_data
        
    def update(self, target_index: int, target_data: int):
        self.raw_data[target_index] = target_data
        
        each_size = len(self.deco_data)
        deco_index = int(math.floor(target_index/each_size))
        
        self.deco_data[deco_index] = self.op(self.raw_data[each_size*deco_index: each_size *(deco_index+1)])
        
    def query(self, start_pos: int, end_pos: int):
        # 愚直に探すところを見つける        
        start_naive = (start_pos, len(self.deco_data)*int(math.ceil(start_pos/len(self.deco_data))))
        end_naive = (len(self.deco_data)*int(math.ceil(end_pos/len(self.deco_data))), end_pos)
        
        deco_check_index = (int(math.ceil(start_pos/len(self.deco_data))), int(math.ceil(end_pos/len(self.deco_data))))
        
        target = self.deco_data[deco_check_index[0]: deco_check_index[1]]+self.raw_data[start_naive[0]:start_naive[1]]+self.raw_data[end_naive[0]:end_naive[1]]
        
        return self.op(target)
        
if __name__ =='__main__':
    num_element, query_num = zip(int(i) for i in input().split(' '))
    data = sqrt_deco(num_element)
    
    for i in range(query_num):
        order, first, second = zip([int(i) for i in input()])
        if order == 0:
            data.update(first, second)
        else order == 1:
            print(data.query(first, second))

Submission status: Runtime Error

Solution code:
import sys;

def init(n_):
    length = 1;
    while(length < n_):
        length*=2
    element=[0]*(2*length-1)
    for i in range(2*length-1):
        element[i] = initial
    return element

def update(k,a,element):
    k+=n
    element[k]=a
    while(k > 0):
        k = (int)((k-1)/2)
        element[k] = min(element[k*2+1],element[k*2+2])

def findmin(a, b):
    return findquery(a,b+1,0,0,n)

def findquery(a, b, k, l, r):
    if(r <= a or b <= l):
        return initial
    if(a <= l and r <= b):
        return element[k]

    vl = findquery(a,b,k*2+1,l,(int)((l+r)/2+0.5))
    vr = findquery(a,b,k*2+2,(int)((l+r)/2),r)
    return min(vl,vr)

n,q = map(int, input().split());

initial = pow(2,31)-1
element = init(n)

for i in range(q):
    query,key,value = map(int, input().split());
    if(query == 0):
        update(key,value,element)
    else :
        print(findmin(key,value))

Submission status: Runtime Error

Solution code:
import sys

def initRMQ(n, D):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(2147483647)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    return query(a, b + 1, 0, 0, n)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 2147483647

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((1 + r)/2))
    vr = query(a, b, k*2 + 2, int((1 + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, q = map(int, input().split())

    D = []
    n_ = initRMQ(n, D)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findMin(x, y))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


def initRMQ(n, D):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(2147483647)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    return query(a, b + 1, 0, 0, n)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 2147483647

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((1 + r)/2))
    vr = query(a, b, k*2 + 2, int((1 + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, q = map(int, input().split())

    D = []
    n_ = initRMQ(n, D)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findMin(x, y))