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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import math
import sys

INIT_MAX = pow(2, 31) - 1


class RMQ(object):
    __slots__ = ('queries', 'ext_heap_length', 'dat')

    def __init__(self, in_data):
        """
        Init a SegmentTree with update and find for range minimum queries.
        """
        n_num, q_num = map(int, in_data[0].split())
        self.queries = map(lambda x: x.split(), in_data[1:])
        self.ext_heap_length = pow(2, math.ceil(math.log2(n_num)))
        self.dat = [INIT_MAX] * (2 * self.ext_heap_length - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.ext_heap_length - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, left=0, right=float('inf')):
        if right <= s or t <= left:
            return INIT_MAX
        elif s <= left <= right <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, left, (left + right) // 2)
            vr = self.find(s, t, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)

    def cmd_exec(self):
        for query in self.queries:
            cmd, ele_1, ele_2 = map(int, query)
            if cmd == 0:
                self.update(ele_1, ele_2)
            elif cmd == 1:
                # assert ele_1 <= ele_2
                res = self.find(s=ele_1, t=ele_2 + 1, right=self.ext_heap_length)
                print(res)

        return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    case = RMQ(in_data=_input)
    case.cmd_exec()

Submission status: Accepted

Solution code:
def update(i, x):
    i += base
    st[i] = x
    while i>0:
        i = (i-1)//2
        st[i] = min(st[i*2+1], st[i*2+2])


def find(a, b):
    return _find(a, b+1, 0, 0, n)


def _find(a, b, k, l, r):
    if b <= l or r <= a:
        return 2**31-1

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

    rl = _find(a, b, 2*k+1, l, (l+r)/2)
    rr = _find(a, b, 2*k+2, (l+r)/2, r)
    return min(rl, rr)


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

n=1
while(n<=_n):
    n *= 2
base = n-1
st = [2**31-1]*(2*n-1)

for i in range(q):
    (c, l, r) = map(int, input().split())
    if c:
        print(find(l, r))
    else:
        update(l, r)

Submission status: Accepted

Solution code:
import sys

inf = (1 << 31) - 1

def solve():
    n, q = map(int, sys.stdin.readline().split())

    sg = SegTree(n)

    for qi in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            sg.update(x, y)
        else:
            ans = sg.find(x, y + 1, 0, 0, 2**sg.d)
            print(ans)

        # print(sg.a)

class SegTree:
    def __init__(self, n):
        self.d = 0

        while (2**self.d) < n:
            self.d += 1

        self.a = [inf] * (2**(self.d+1) - 1)

    def update(self, i, x):
        pos = i + 2**self.d - 1
        self.a[pos] = x

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

        return

    def find(self, s, t, k, l, r):
        if r <= s or t <= l:
            return inf
        if s <= l and r <= t:
            return self.a[k]

        vl = self.find(s, t, 2*k + 1, l, (l + r) // 2)
        vr = self.find(s, t, 2*k + 2, (l + r) // 2, r)

        return min(vl, vr)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

inf = (1 << 31) - 1

def solve():
    n, q = map(int, sys.stdin.readline().split())

    a = [inf] * n
    sg = SegTree(a)

    for qi in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            sg.update(x, y)
        else:
            ans = sg.find(x, y + 1, 0, 0, 2**sg.depth)

            print(ans)


class SegTree:

    def __init__(self, a):
        self.n = len(a)
        self.depth = 0

        while 2**self.depth < self.n:
            self.depth += 1

        self.dat = [inf] * (2**(self.depth + 1) - 1)

        self.dat[2**self.depth - 1:2**self.depth - 1 + self.n] = a[:]

        for i in range(2**self.depth - 2, -1, -1):
            self.dat[i] = min(self.dat[2*i + 1], self.dat[2*i + 1])

    def update(self, i, x):
        i += 2**self.depth - 1
        self.dat[i] = x

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

        return

    def find(self, s, t, k, left, right):
        if t <= left or right <= s:
            return inf
        if s <= left and right <= t:
            return self.dat[k]

        vl = self.find(s, t, 2*k + 1, left, (left + right) // 2)
        vr = self.find(s, t, 2*k + 2, (left + right) // 2, right)

        return min(vl, vr)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math, sys
MAX = pow(2, 31) - 1

#??°????????????????????§????°????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [MAX] * (2 * self.TreeRange - 1)

    def update(self, i, x):
        i += self.TreeRange - 1
        self.List[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] = min (self.List[i * 2 + 1], self.List[i * 2 + 2])

    def find(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°?????§???????????????
        if right <= s or t <= left:
            return MAX
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.find(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.find(s, t, i * 2 + 2, (left + right) // 2, right)
            return min(l, r)

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.update(x, y)
    elif cmd == 1:
        print(ST.find(x,y + 1, right = ST.TreeRange))

Submission status: Accepted

Solution code:
import math
n, q = map(int, input().split())
l = 1 << math.ceil(math.log(n, 2))
inf = 2**31-1
a = [inf]*(2*l-1)

def set_value(i, num):
    k = l-1+i
    a[k] = num
    while k > 0:
        k = (k-1)//2
        num = min(a[2*k+1], a[2*k+2])
        if a[k] == num:
            break
        else:
            a[k] = num
            
def get_minimum(x, y, k=0, l=0, r=l-1):
    if x == l and r == y:
        return a[k]
    elif not l <= x <= y <= r:
        return inf
    mid = (l+r)//2
    left_value = get_minimum(x, min(mid, y), 2*k+1, l, mid)
    right_value = get_minimum(max(mid+1, x), y, 2*k+2, mid+1, r)
    return min(left_value, right_value)
    
ans = []
for _ in [None]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        set_value(x, y)
    else:
        ans.append(get_minimum(x, y))
print("\n".join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
import math


class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree"]

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree_size = 2 * self.elem_size
        self.tree = [default]*self.elem_size + a + [default]*(self.elem_size - real_size)
        self.init_tree()

    def init_tree(self):
        tree = self.tree
        for i in range(self.elem_size-1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1)+1]
            # ===== ??????????????´???????????? =====
            tree[i] = left if left < right else right

    def get_range_index(self, x: int, y: int, k: int = 1, l_end: int = 0, r_end: int = None):
        '''[x, y), tree[k], [l_end, r_end)'''
        if r_end is None:
            r_end = self.elem_size

        if l_end == x and y == r_end:
            return [k]

        mid = (l_end + r_end) // 2
        left_y = y if y < mid else mid
        right_x = x if x > mid else mid

        left = self.get_range_index(x, left_y, k << 1, l_end, mid) if x < left_y else []
        right = self.get_range_index(right_x, y, (k << 1)+1, mid, r_end) if right_x < y else []
        return left + right

    def get_value(self, x: int, y: int):
        tree = self.tree
        index_list = self.get_range_index(x, y)

        # ===== ??????????????´???????????? =====
        return min(tree[n] for n in index_list)

    def update_tree(self, k: int):
        tree = self.tree

        while k > 1:
            k >>= 1
            left, right = tree[k << 1], tree[(k << 1)+1]
            # ===== ??????????????´???????????? =====
            tree[k] = left if left < right else right

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rmq = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rmq.set_value(x, y, "=")
    else:
        ans.append(rmq.get_value(x, y+1))
print("\n".join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
import math


class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree"]

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree_size = 2 * self.elem_size
        self.tree = [default]*self.elem_size + a + [default]*(self.elem_size - real_size)
        self.init_tree()

    def init_tree(self):
        tree = self.tree
        for i in range(self.elem_size-1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1)+1]
            # ===== ??????????????´???????????? =====
            tree[i] = left if left < right else right

    def get_range_indexes(self, x: int, y: int):
        '''[x, y), tree[k], [l_end, r_end)'''
        l, r = x+self.elem_size, y+self.elem_size
        indexes = []
        append = indexes.append
        while l < r:
            if l & 1:
                append(l)
                l += 1
            if r & 1:
                r -= 1
                append(r)
            l, r = l >> 1, r >> 1

        return indexes

    def get_value(self, x: int, y: int):
        tree = self.tree
        index_list = self.get_range_indexes(x, y)

        # ===== ??????????????´???????????? =====
        return min(tree[n] for n in index_list)

    def update_tree(self, k: int):
        tree = self.tree

        while k > 1:
            k >>= 1
            left, right = tree[k << 1], tree[(k << 1)+1]
            # ===== ??????????????´???????????? =====
            tree[k] = left if left < right else right

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rmq = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rmq.set_value(x, y, "=")
    else:
        ans.append(rmq.get_value(x, y+1))
print("\n".join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
class SegTreeMin:
    def __init__(self, n):
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [(1 << 31) - 1] * (n2 << 1)
        self.output = []

    def update(self, i, x):
        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, s, t):
        self.output.append(self._get_min(s, t + 1, 1, 0, self.n2))

    def _get_min(self, a, b, k, l, r):
        if r <= a or b <= l:
            return (1 << 31) - 1
        if a <= l and r <= b:
            return self.tree[k]
        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))

    def print(self):
        print('\n'.join(map(str, self.output)))


n, q = map(int, input().split())
st = SegTreeMin(n)
fs = [st.update, st.get_min]
for c, x, y in (map(int, input().split()) for _ in range(q)):
    fs[c](x, y)
st.print()

Submission status: Accepted

Solution code:
class SegTreeMin:
    SENTINEL = (1 << 31) - 1
    output = []

    def __init__(self, n):
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.SENTINEL] * (n2 << 1)

    def update(self, i, x):
        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, s, t):
        self.output.append(self._get_min(s, t + 1, 1, 0, self.n2))

    def _get_min(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.SENTINEL
        if a <= l and r <= b:
            return self.tree[k]
        m = (l + r) // 2
        k <<= 1
        return min(
            self._get_min(a, b, k, l, m),
            self._get_min(a, b, k + 1, m, r))

    def print(self):
        print('\n'.join(map(str, self.output)))


n, q = map(int, input().split())
st = SegTreeMin(n)
fs = [st.update, st.get_min]
for c, x, y in (map(int, input().split()) for _ in range(q)):
    fs[c](x, y)
st.print()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


class RMQ(object):
    INT_MAX = 2**31 - 1

    def __init__(self, nn):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        self.dat = [RMQ.INT_MAX] * ((2 * self.n)-1)

    def update(self, k, a):
        # A[k]???a?????´??°?????????????????°???????????¨?????´??°
        k += (self.n - 1)
        self.dat[k] = a

        while k > 0:
            k = (k - 1) // 2        #  ??????index??????
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2]) #  ???????????¨??????????????????????°?????????????????????´??°

    def query(self, a, b, k, l, r):
        # [a, b)???????°????????±??????? (0????????§b???????????????)
        # ??????????????¨?????????query(a, b, 0, 0, n)?????¢??§??????????????????k, l, r???????????????????????´??°?????????
        if r <= a or b <= l:        #  ?????????????????§??¨??????????????????
            return RMQ.INT_MAX
        if a <=l and r <= b:
            return self.dat[k]           #  ???????????°???????????????????????§????????°????????¨??????????????????????°?????????????????????????
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2) #  ????????°????????????????°????
            vr = self.query(a, b, k*2+2, (l+r)//2, r) #  ????????°????????????????°????
            return min(vl, vr)

    def find(self, s, t):
        return self.query(s, t+1, 0, 0, self.n)


def main(args):
    n, q = map(int, input().split(' '))

    rq = RMQ(n)
    for _ in range(q):
        com, x, y = map(int, input().split(' '))
        if com == 0:
            rq.update(x, y)
        elif com == 1:
            res = rq.find(x, y)
            print(res)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n,q = LI()
    a = [LI() for _ in range(q)]
    def f(a,b):
        if a < b:
            return a
        return b
    seg = Seg(n+10, 2**31-1, f)
    r = []
    for c,x,y in a:
        if c == 0:
            seg.update(x,y)
        else:
            r.append(seg.query(x,y+1))

    return '\n'.join(map(str,r))


print(main())

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a == b:
            return self.segtree[self.length - 1 + a]
        elif a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return self.ini_num
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return self.ini_num
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = map(int, input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = map(int, input().split(" "))
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return self.ini_num
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = map(int, input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in [0] * query:
    com, i, n = map(int, input().split(" "))
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Accepted

Solution code:
class SegmentTree():
	def __init__(self,n):
		self.dat = [INF for _ in range(n*2-1)]
		#index n???????????????????????¢?????????:
		#???????????? : (n-1)//2
		#???????????? : (2n+1) , (2n+2)
		self.n = n

	def update (self,node_index,value):
		""" index?????????value????????´?????? """
		index = node_index + (self.n-1) #node_index????????????dot???index?????????
		self.dat[index] = value

		#?????°????????????????????????????????´????????????
		while index > 0 :
			index = (index - 1) // 2				 #???????????????????????£???
			self.dat[index] = min([self.dat[index*2+1],self.dat[index*2+2]]) #??????????????????????????????

	def querry (self,left,right,nowNode,nowLeft,nowRight):
		"""[left,right):??¢?´¢??????,noeNode:?????¨????????????,[nowLeft,nowRight):?????¨?????????????????????"""

		# ??????????????¶??£????????????
		if nowRight < left or nowLeft > right:
			return INF

		# ?????¨?????¢?´¢???????????¨????????????????????????????????????
		if left <= nowLeft and nowRight <= right:
			return self.dat[nowNode]

		# ???????????????????????????????????¨???????????????
		else:
			value_left =self.querry(left,right,2*nowNode+1,nowLeft,(nowLeft+nowRight)//2)
			value_right = self.querry(left,right,2*nowNode+2,(nowLeft+nowRight)//2+1,nowRight)
			return min([value_left,value_right])

	def DEBUG_dat(self):
		print(self.dat)
		

if __name__ == "__main__":
	# ??????????????????
	INF = 2147483647
	n ,q  = map(int,input().split(" "))
	result = []

	for i in range(1,20):
		if 2 ** i >= n:
			min_pow2 = 2 **  i
			break

	tree = SegmentTree(min_pow2)

	for i in range(q):
		com,x,y = map(int,input().split(" "))
		if com == 0:
			tree.update(x,y)
		else:
			result.append(tree.querry(x,y,0,0,min_pow2-1))

	for i in result:
		print(i)

Submission status: Accepted

Solution code:
import math


class RMQ:
    def __init__(self, n):
        k = 1
        while k < n:
            k *= 2
        self.N = k
        self.node = [float("inf")] * (int(2 * self.N - 1))

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

    def _find(self, a, b, i, l, r):
        if r <= a or b <= l:
            return float("inf")
        elif a <= l and r <= b:
            return self.node[i]

        else:
            mid = (l + r) // 2
            return min(self._find(a, b, 2 * i + 1, l, mid), self._find(a, b, 2 * i + 2, mid, r))

    def find(self, a, b):
        return self._find(a, b, 0, 0, self.N)


n, q = map(int, input().split())
rmq = RMQ(n)
inf = 2147483647
for j in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        rmq.update(x, y)
    else:
        m = rmq.find(x, y + 1)
        if m == float("inf"):
            print(inf)
        else:
            print(m)

Submission status: Accepted

Solution code:
import math


class RMQ:
    def __init__(self, n):
        k = 1
        while k < n:
            k *= 2
        self.N = k
        self.node = [float("inf")] * (2 * self.N - 1)

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

    def _find(self, a, b, i, l, r):
        if r <= a or b <= l:
            return float("inf")
        elif a <= l and r <= b:
            return self.node[i]

        else:
            mid = (l + r) // 2
            return min(self._find(a, b, 2 * i + 1, l, mid), self._find(a, b, 2 * i + 2, mid, r))

    def find(self, a, b):
        return self._find(a, b, 0, 0, self.N)


n, q = map(int, input().split())
rmq = RMQ(n)
inf = 2147483647
for j in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        rmq.update(x, y)
    else:
        m = rmq.find(x, y + 1)
        if m == float("inf"):
            print(inf)
        else:
            print(m)

Submission status: Accepted

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,length

def update(k,a,element):
    k+=n-1
    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,n = 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: Accepted

Solution code:

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

n_ = 1 # 実際に確保した配列のサイズ
while n_ < n:
  n_ *= 2

initv = pow(2, 31)-1
seg_tree = [initv for i in range(2*n_-1)]

def update(i, x):
  i += n_ - 1
  seg_tree[i] = x
  while i > 0 :
    i = int((i - 1)/2)
    seg_tree[i] = min(seg_tree[i*2+1], seg_tree[i*2+2])

def findMin(s, t):
  return query(s, t+1, 0, 0, n_)

def query(a, b, k, l, r):
  if r <= a or b <= l :
    return initv
  if a <= l and r <= b:
    return seg_tree[k]

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


output = []

for i in range(q):
  line = list(map(int, input().split()))

  if line[0] == 0:
    update(line[1], line[2])

  else :
    output.append(findMin(line[1],line[2]))


for ans in output:
  print(ans)

Submission status: Accepted

Solution code:
# Range Minimum Query (RMQ)
INF = 2**31 - 1
D = [INF]
[n, q] = list(map(int, input().split()))

def initRMQ(n_):
    global D, n
    size = 1
    while size < n_:
        size *= 2
    i = 1
    while i <= 2*size - 1 - 1:
        D.append(INF)
        i += 1
    n = size

def update(k, a):
    global n
    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 query(a, b, k, l, r):
    global INF, D
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return D[k]

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

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

initRMQ(n)

for i in range(q):
    data = list(map(int, input().split()))
    if data[0] == 0:
        update(data[1], data[2])
    if data[0] == 1:
        print(findMin(data[1], data[2]))