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: Accepted

Solution code:
class SegmentTree():
    def __init__(self, n, inf=float('inf')):
        self.n = 2**(n-1).bit_length()
        self.inf = inf
        self.data = [inf]*(2*self.n)

    def update(self, k, a):
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = min(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        L = l+self.n
        R = r+self.n
        ret = self.inf
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R-1])
            if L & 1:
                ret = min(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


n, q = map(int, input().split())
T = SegmentTree(n, 2**31-1)

ans = []
for _ in range(q):
    c, x, y = map(int, input().split())
    if c:
        ans.append(T.query(x, y+1))
    else:
        T.update(x, y)
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
M = 2147483647
a = [M for i in range(1000000)]

def j_min(x,y):
    if x < y:return x
    else: return y

def find(x,y,i,l,r):
    if r<=x or y<=l:return M
    if x<=l and r<=y: return a[i]
    return j_min(find(x,y,i*2,l,(l+r)/2),find(x,y,i*2+1,(l+r)/2,r))

if __name__=='__main__':
    n, m = (int(x) for x in input().split())
    t=1
    while t<n :t *= 2

    for i in range(m-1,-1,-1):
        com,x,y = (int(x) for x in input().split())
        if com :
            #continue
            print(find(x,y+1,1,0,t))
        else:
            x+=t
            a[x]=y
            while isinstance(x, int) or x >= 2:
               a[int(x/2)]=j_min(a[int(x)],a[int(x)^1])
               x/=2

Submission status: Accepted

Solution code:
M = 2147483647
a = [M for i in range(500000)]

def j_min(x,y):
    if x < y:return x
    else: return y

def find(x,y,i,l,r):
    if r<=x or y<=l:return M
    if x<=l and r<=y: return a[i]
    return j_min(find(x,y,i*2,l,(l+r)/2),find(x,y,i*2+1,(l+r)/2,r))

if __name__=='__main__':
    n, m = (int(x) for x in input().split())
    t=1
    while t<n :t *= 2

    for i in range(m-1,-1,-1):
        com,x,y = (int(x) for x in input().split())
        if com :
            #continue
            print(find(x,y+1,1,0,t))
        else:
            x+=t
            a[x]=y
            while isinstance(x, int) or x >= 2:
               a[int(x/2)]=j_min(a[int(x)],a[int(x)^1])
               x/=2

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=2**31-1

class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """
 
    def __init__(self, n):
        """
        :param n: 要素数
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [INF] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1
 
    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_min(a, b, 1, 0, self.n2)
 
    def _get_min(self, a, b, k, l, r):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合はINF
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return INF
        # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return min(
            self._get_min(a, b, k << 1, l, m),
            self._get_min(a, b, (k << 1) + 1, m, r)
        )

N,Q=MAP()
st=SegTreeMin(N)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        st.update(x, y)
    else:
        print(st.get_min(x, y+1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc014/submissions/3935971
class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op

        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1

        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

n, q = map(int, input().split())
seg = SegmentTree([(1<<31)-1]*n, (1<<31)-1, min)
for _ in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        seg.set_value(x, y)
    else:
        print(seg.get_value(x, y+1))

Submission status: Accepted

Solution code:
import operator


class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=0):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        """
        # size 以上である最小の 2 冪
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._tree = [default for _ in range(self._size * 2 - 1)]
        self._fn = fn

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N, Q = list(map(int, input().split()))
com, X, Y = zip(*[input().split() for _ in range(Q)])
X = list(map(int, X))
Y = list(map(int, Y))

if __name__ == '__main__':
    st = SegmentTree(size=N + 1, fn=min, default=2 ** 31 - 1)
    for c, x, y in zip(com, X, Y):
        if c == '0':
            st.set(x, y)
        if c == '1':
            print(st.get(x, y + 1))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
 
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
 
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
 
 
ans = []
for q in range(Q):
    t, x, y = map(int, input().split())
    if t:
        ans.append(str(query(x, y+1)))
    else:
        update(x, y)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
import itertools

class RMQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz < n: self.sz = self.sz << 1
        self.dat = [self.inf] * (2 * self.sz - 1)
    
    def update(self, idx, x):
        idx += self.sz - 1
        self.dat[idx] = x
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
            
    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)
            
    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return sys.maxint
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
                        self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    n, q = line.split()
    n, q = int(n), int(q)
    rmq = RMQ(n)
    
    for i in range(q):
        line = sys.stdin.readline()
        op, a, b = line.split()
        op, a, b = int(op), int(a), int(b)
        if op == 0: 
            rmq.update(a, b)
        else: 
            sys.stdout.write(str(rmq.query(a, b + 1)) + '\n')

Submission status: Accepted

Solution code:
import sys
import itertools
 
class RMQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz <= n: self.sz = self.sz << 1
        self.dat = [self.inf] * (2 * self.sz - 1)
     
    def update(self, idx, x):
        idx += self.sz - 1
        self.dat[idx] = x
        while idx > 0:
            idx = (idx - 1) >> 1
            self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
             
    def query(self, a, b):
        return self.query_help(a, b, 0, 0, self.sz)
             
    def query_help(self, a, b, k, l, r):
        if r <= a or b <= l:
            return sys.maxint
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
                        self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
     
     
if __name__ == '__main__':
    line = sys.stdin.readline()
    n, q = line.split()
    n, q = int(n), int(q)
    rmq = RMQ(n)
     
    for i in range(q):
        line = sys.stdin.readline()
        op, a, b = line.split()
        op, a, b = int(op), int(a), int(b)
        if op == 0: 
            rmq.update(a, b)
        else: 
            sys.stdout.write(str(rmq.query(a, b + 1)) + '\n')

Submission status: Accepted

Solution code:
class RangeMinimumQuery(object):

    def __init__(self, size):
        self.size = 1
        while self.size < size:
            self.size *= 2
        self.data = [float("inf") for _ in xrange(self.size*2+2)]

    def update(self, idx, value):
        k = idx + self.size - 1
        self.data[k] = value
        while k > 0:
            k = (k - 1) / 2
            self.data[k] = min(self.data[k*2+1], self.data[k*2+2])

    def find(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return float("inf")
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)/2)
            vr = query(k*2+2, (left+right)/2, right)
            return min(vl, vr)
        return query(0, 0, self.size)


def main():
    n, q = map(int, raw_input().split())
    inf = (1 << 31) - 1
    rmq = RangeMinimumQuery(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            rmq.update(x, y)
        else:
            v = rmq.find(x, y+1)
            print v if v != float("inf") else inf

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
class segment_tree:
    
    # self.table is 1-indexed
    # math.log2 not implemented 3.2.3
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query(self.table[2 * i], self.table[2 * i + 1])

    # [l, r] closed-interval
    def find(self, l, r):
        return self.query(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def update(self, i, x):
        i += self.offset
        self.table[i] = x
        while 1 < i:
            i >>= 1
            self.table[i] = self.query(self.table[2 * i], self.table[2 * i + 1])

import sys
f = sys.stdin

n, q = map(int, f.readline().split())

rmq = segment_tree([(1 << 31) - 1] * n, min, float('inf'))

function = (rmq.update, lambda x, y:print(rmq.find(x, y)))
for com, x, y in (map(int, f.readline().split()) for _ in range(q)):
    function[com](x, y)

Submission status: Accepted

Solution code:
class RangeMinQuery:
    inf = 2 ** 31 - 1
    def __init__(self, N):
        self.n = 1
        while self.n < N: self.n *= 2
        self.dat = [self.inf] * (2 * self.n - 1)
 
    def update(self, k, x):
        k += self.n - 1
        self.dat[k] = x
        while (k > 0):
            k = (k - 1) / 2
            self.dat[k] = min(self.dat[2 * k + 1], self.dat[2 * k + 2])
 
    # [a, b); call query(a, b)
    def query(self, a, b, k = 0, l = 0, r = -1):
        if r == -1: r = self.n
        if r <= a  or b <= l: return self.inf
        if a <= l and r <= b: return self.dat[k]
 
        vl = self.query(a, b, 2 * k + 1, l, (l + r) / 2)
        vr = self.query(a, b, 2 * k + 2, (l + r) / 2, r)
        return min(vl, vr)
 
n, q = map(int, raw_input().split())
rmq = RangeMinQuery(n)
for i in xrange(q):
    c, x, y = map(int, raw_input().split())
    if c == 0:
        rmq.update(x, y)
    else:
        print rmq.query(x, y + 1)

Submission status: Accepted

Solution code:
class RangeMinimumQuery:
    def __init__(self, N, INF=float('inf')):
        self.N = 1
        while self.N < N:
            self.N <<= 1
        self.INF = INF
        self.segtree = [self.INF] * (self.N * 2 - 1)

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.segtree[i] = min(self.segtree[2*i+1], self.segtree[2*i+2])

    def query(self, low, high, k=0, left=0, right=-1):
        if right == -1: right = self.N
        if right <= low or high <= left: return self.INF

        if low <= left and right <= high:
            return self.segtree[k]
        else:
            mid = (left + right) // 2
            return min(self.query(low, high, 2*k+1, left, mid), 
                       self.query(low, high, 2*k+2, mid, right))

N, Q = map(int, input().split())
rmq = RangeMinimumQuery(N, INF=(1<<31)-1)
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        rmq.update(x, y)
    elif com == 1:
        print(rmq.query(x, y+1))
#    print(rmq.segtree[:rmq.N*2-1])

Submission status: Accepted

Solution code:
import math
class RangeMinimumQuery:
    """
    RangeMinimumQuery by Segment Tree
    query:
    1. update(i, val): update i-th value to val
    2. query(low, high): find minimun value in [low, high)
    time complexity: O(log n)
    space complexity: O(2n)    
    """
    def __init__(self, N, INF=float('inf')):
        self.N = 1 << math.ceil(math.log(N, 2))
        self.INF = INF
        self.segtree = [self.INF] * (self.N * 2 - 1)

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.segtree[i] = min(self.segtree[2*i+1], self.segtree[2*i+2])

    def query(self, low, high, k=0, left=0, right=-1):
        if right == -1: right = self.N
        if right <= low or high <= left: return self.INF

        if low <= left and right <= high:
            return self.segtree[k]
        else:
            mid = (left + right) // 2
            return min(self.query(low, high, 2*k+1, left, mid), 
                       self.query(low, high, 2*k+2, mid, right))

N, Q = map(int, input().split())
rmq = RangeMinimumQuery(N, INF=(1<<31)-1)
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        rmq.update(x, y)
    elif com == 1:
        print(rmq.query(x, y+1))

Submission status: Accepted

Solution code:
# coding: utf-8

n, q = map(int,raw_input().split())
A = [2**31-1 for i in xrange(100000)]
B = [2**31-1 for i in xrange(101)]

def update(i,x):
    if A[i] == 2**31-1:
        A[i] = x
        B[i/1000] = min(x, B[i/1000])
    else:
        A[i] = x
        MIN = 2**31-1
        for j in xrange(i/1000 * 1000, (i/1000 + 1) * 1000):
            if A[j] < MIN:
                MIN = A[j]
        B[i/1000] = MIN

def find(s,t):
    MIN = 2**31-1
    if s/1000 == t/1000 or s/1000 + 1 == t/1000:
        for i in xrange(s, t+1):
            if A[i] < MIN:
                MIN = A[i]
    else:
        #left range
        for i in xrange(s, (s/1000 + 1) * 1000):
            if A[i] < MIN:
                MIN = A[i]
        #middle range
        for j in xrange(s/1000 + 1, t/1000):
            if B[j] < MIN:
                MIN = B[j]
        
        #right range
        for i in xrange(t/1000 * 1000, t+1):
            if A[i] < MIN:
                MIN = A[i]
    print MIN   
    
for i in xrange(q):
    com, s, t = map(int,raw_input().split())
    if com: #find
        find(s,t)
    else: #update
        update(s,t)

Submission status: Accepted

Solution code:
import time

N, Q = map(int, input().split())
SegTree = [0 for i in range(4*N)]

def modify(i, left, right, value, pos=-1):
    global SegTree
    if left==right:
        if pos != -1:
            SegTree[i] = value
        else:
            SegTree[i] = 2147483647
        return

    mid = int((left+right)/2)
    if pos==-1 or pos<=mid:
        modify(i*2, left, mid, value, pos)
    if pos==-1 or pos>mid:
        modify(i*2+1, mid+1, right, value, pos)
    
    SegTree[i] = min(SegTree[i*2], SegTree[i*2+1])

def query_min(i, L, R, left, right):
    if right < L or R < left:
        return 2147483647
    if left<=L and R<=right:
        return SegTree[i]
    mid = int((L+R)/2)
    return min(query_min(2*i, L, mid, left, right),
               query_min(2*i+1, mid+1, R, left, right))

modify(i=1, left=0, right=N-1, value=0, pos=-1) #init

for querys in range(Q):
    t, a, b = map(int, input().split())
    if t == 0:
        modify(i=1, left=0, right=N-1, pos=a, value=b)
    else:
        print( query_min(i=1, L=0, R=N-1, left=a, right=b) )

Submission status: Accepted

Solution code:
# coding: utf-8

n, q = map(int,raw_input().split())
A = [(1<<31) - 1 for i in xrange(100000)]
B = [(1<<31) - 1 for i in xrange(101)]
 
def update(i,x):
    if A[i] == (1<<31) - 1:
        A[i] = x
        B[i/1000] = min(x, B[i/1000])
    else:
        A[i] = x
        MIN = (1<<31) - 1
        for j in xrange(i/1000 * 1000, (i/1000 + 1) * 1000):
            if A[j] < MIN:
                MIN = A[j]
        B[i/1000] = MIN
 
def find(s,t):
    MIN = (1<<31) - 1
    if s/1000 == t/1000 or s/1000 + 1 == t/1000:
        for i in xrange(s, t+1):
            if A[i] < MIN:
                MIN = A[i]
    else:
        #left range
        for i in xrange(s, (s/1000 + 1) * 1000):
            if A[i] < MIN:
                MIN = A[i]
        #middle range
        for j in xrange(s/1000 + 1, t/1000):
            if B[j] < MIN:
                MIN = B[j]
         
        #right range
        for i in xrange(t/1000 * 1000, t+1):
            if A[i] < MIN:
                MIN = A[i]
    print MIN   
     
for i in xrange(q):
    com, s, t = map(int,raw_input().split())
    if com: #find
        find(s,t)
    else: #update
        update(s,t)

Submission status: Accepted

Solution code:
from math import sqrt, ceil

def_val = 2 ** 31 - 1
n, q = map(int, input().split())
unit = ceil(sqrt(n))

l = [(def_val, [def_val] * unit) for _ in range(unit)]

while q:
    op, s, t = map(int, input().split())
    sd, sm = s // unit, s % unit
    if op:
        td, tm = t // unit, t % unit
        if sd == td:
            print(min(l[sd][1][sm:tm + 1]))
        else:
            unit_min = min((tup[0] for tup in l[sd + 1:td]), default=def_val)
            s_min = min(l[sd][1][sm:], default=def_val)
            t_min = min(l[td][1][:tm + 1], default=def_val)
            print(min(unit_min, s_min, t_min))
    else:
        unit_list = l[sd][1]
        unit_list[sm] = t
        l[sd] = (min(unit_list), unit_list)
    q -= 1

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import math

# main
n, q = map(int, input().split())
b_size = math.ceil(math.sqrt(n))
b_len = math.ceil(n/b_size)
a = [2 ** 31 - 1 for i in range(n)]
b = [min(a[b_size * i:b_size * (i + 1)]) for i in range(b_len)]
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        # update
        a[x] = y
        # update b
        index = x // b_size
        b[index] = min(a[index * b_size:(index + 1) * b_size])

    else:
        # find
        target = []
        x_index = x // b_size
        y_index = y // b_size
        x_mod = x % b_size
        y_mod = y % b_size
        if x_index == y_index:
            target.extend(a[x:y + 1])
        else:
            if x_mod == 0:
                target.append(b[x_index])
            else:
                target.extend(a[x:(x_index + 1) * b_size])

            if y_mod == b_size - 1:
                target.append(b[y_index])
            else:
                target.extend(a[y_index * b_size:y + 1])

            if x_index + 1 <= y_index - 1:
                target.append(min(b[x_index + 1 : y_index]))
        print(min(target))

Submission status: Accepted

Solution code:
class SegmentTree(object):
 
    def __init__(self, size, op=min, init=float("inf")):
        self.size = 1
        self.op = op
        self.init = init
        while self.size < size:
            self.size *= 2
        self.data = [init] * (self.size*2+2)
 
    def update(self, idx, value):
        k = idx + self.size - 1
        self.data[k] = value
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[k*2+1], self.data[k*2+2])
 
    def find(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return self.init
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)//2)
            vr = query(k*2+2, (left+right)//2, right)
            return self.op(vl, vr)
        return query(0, 0, self.size)
 

if __name__ == "__main__":
    n, q = list(map(int, input().split()))
    tree = SegmentTree(n, init=(1<<31)-1)
    for _ in range(q):
        com, x, y = list(map(int, input().split()))
        if com == 0:
            tree.update(x, y)
        else:
            print(tree.find(x, y+1))

Submission status: Accepted

Solution code:
n, q = map(int, raw_input().split())
n0 = 2**n.bit_length()
INF = 2**31-1
data = [INF]*(n0*2)
def update(k, a):
    k += n0 - 1
    data[k] = a
    while k:
        k = (k - 1) / 2
        data[k] = min(data[2*k+1], data[2*k+2])
def query(a, b, k, l, r):
    if b <= l or r <= a:
        return INF
    if a <= l and r <= b:
        return data[k]
    vl = query(a, b, 2*k+1, l, (l + r) / 2)
    vr = query(a, b, 2*k+2, (l + r) / 2, r)
    return min(vl, vr)
def find(s, t):
    print query(s, t+1, 0, 0, n0)
for i in xrange(q):
    com, x, y = map(int, raw_input().split())
    [update, find][com](x, y)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

class Segtree():
    INT_MAX=2**31-1
    def __init__(self,n):
        self.n=1
        while self.n<n:
            self.n=self.n*2
        self.ary=[self.INT_MAX]*(2*self.n-1)

    def min_update(self,k,a):
        k+=self.n-1
        self.ary[k]=a
        while k>0:
            k=(k-1)/2
            self.ary[k]=min(self.ary[k*2+1],self.ary[k*2+2])

    def min_query(self,a,b,k,l,r):
        if r==-1:r=self.n
        if (r<=a or b<=l):return self.INT_MAX
        if (a<=l and r<=b):return self.ary[k]
        else:
            vl=self.min_query(a,b,k*2+1,l,(l+r)/2)
            vr=self.min_query(a,b,2*k+2,(l+r)/2,r)
            return min(vl,vr)

    def find_min(self,s,t):
        return self.min_query(s,t+1,0,0,-1)

n,q=map(int,raw_input().split())
st=Segtree(n)
for i in xrange(q):
    com,x,y=map(int,raw_input().split())
    if com==0:
        st.min_update(x,y)
    if com==1:
        print(st.find_min(x,y))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
 
def main(init=int(2**31-1), readline=stdin.readline):
    n, q = (int(s) for s in readline().split())
 
    a = [init] * n
    b = [init] * ((n // 100) + 1)
 
    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            bx = x - (x % 100) + 100
            by = y - (y % 100)
            if bx < by:
                m = min(min(a[x:bx]), min(b[bx//100:by//100]),
                        min(a[by:y+1]))
            else:
                m = min(a[x:y+1])
            print(m)
        else:
            a[x] = y
            bx = x - (x % 100)
            b[x//100] = min(a[bx:bx+100])
 
 
main()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())

# make a list whose length is 2^i - 1.
num = 1
max_v = 2147483647

while num < n:
    num *= 2

A = [max_v for i in range(2 * num - 1)]


def update(i, x):
    i += num - 1
    A[i] = x

    while i > 0:
        i = (i - 1) // 2
        A[i] = min(A[i * 2 + 1], A[i * 2 + 2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_v
    if a <= l and r <= b:
        return A[k]
    else:
        vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        ans = find(x, y + 1, 0, 0, num)
        print(ans)

Submission status: Accepted

Solution code:
import math

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

# make a list whose length is 2^i - 1.
n = pow(2, math.ceil(math.log2(n)))
max_v = 2147483647

A = [max_v for i in range(2 * n - 1)]


def update(i, x):
    i += n - 1
    A[i] = x

    while i > 0:
        i = (i - 1) // 2
        A[i] = min(A[i * 2 + 1], A[i * 2 + 2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_v
    if a <= l and r <= b:
        return A[k]
    else:
        vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        ans = find(x, y + 1, 0, 0, n)
        print(ans)

Submission status: Accepted

Solution code:
import math

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

# make a list whose length is 2^i - 1.
n = 2 ** math.ceil(math.log(n, 2))
max_v = 2147483647

A = [max_v for i in range(2 * n - 1)]


def update(i, x):
    i += n - 1
    A[i] = x

    while i > 0:
        i = (i - 1) // 2
        A[i] = min(A[i * 2 + 1], A[i * 2 + 2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_v
    if a <= l and r <= b:
        return A[k]
    else:
        vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        ans = find(x, y + 1, 0, 0, n)
        print(ans)

Submission status: Accepted

Solution code:
import math

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

# make a list whose length is 2^i - 1.
n = 2 ** math.ceil(math.log(n, 2))
max_v = 2147483647

A = [max_v for i in range(2 * n - 1)]


def update(i, x):
    i += n - 1
    A[i] = x

    while i > 0:
        i = (i - 1) // 2
        A[i] = min(A[i * 2 + 1], A[i * 2 + 2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_v
    elif a <= l and r <= b:
        return A[k]
    else:
        vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        ans = find(x, y + 1, 0, 0, n)
        print(ans)