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:

import random


class Node:
    __slots__ = ('x', 'y', 'left', 'right', 'valid')

    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.left = None
        self.right = None
        self.valid = True

    def __str__(self):
        if self.valid:
            return "({} [{},{}] {})".format(self.left, self.x,
                                            self.y, self.right)
        else:
            return "({} *[{},{}] {})".format(self.left, self.x,
                                             self.y, self.right)


class KdTree:
    MAX = 2**31-1

    def __init__(self, size):
        self.root = None
        self.index = [None] * size

    def insert(self, x, y):
        self._delete(self.index[x])
        self.root = self._insert(self.root, x, y)

    def _insert(self, node, x, y, level=0):
        if node is None:
            node = Node(x, y)
            self.index[x] = node
            return node
        if level % 2 == 0:
            if node.x > x:
                node.left = self._insert(node.left, x, y, level+1)
            else:
                node.right = self._insert(node.right, x, y, level+1)
        else:
            if node.y > y:
                node.left = self._insert(node.left, x, y, level+1)
            else:
                node.right = self._insert(node.right, x, y, level+1)
        return node

    def miny(self, x1, x2):
        def _miny(node, y, level):
            if node is None:
                return y
            left, right = self.MAX, self.MAX
            if level % 2 == 0:
                if x2 < node.x:
                    left = _miny(node.left, y, level+1)
                elif x1 > node.x:
                    right = _miny(node.right, y, level+1)
                else:
                    if self._is_valid(node) and node.y < y:
                        y = node.y
                    left = _miny(node.left, y, level+1)
                    if left < y:
                        y = left
                    right = _miny(node.right, y, level+1)
            else:
                if node.y > y:
                    left = _miny(node.left, y, level+1)
                elif node.y < y:
                    if x1 <= node.x <= x2 and self._is_valid(node):
                        left = _miny(node.left, node.y, level+1)
                    else:
                        left = _miny(node.left, y, level+1)
                        if left < y:
                            y = left
                        right = _miny(node.right, y, level+1)
                else:
                    left = _miny(node.left, y, level+1)

            if left < y:
                y = left
            if right < y:
                y = right
            return y

        assert x1 <= x2
        return _miny(self.root, self.MAX, 0)

    def _delete(self, node):
        if node is not None:
            node.valid = False

    def _is_valid(self, node):
        if node is not None:
            return node.valid
        else:
            return False


def run():
    n, q = [int(i) for i in input().split()]
    tree = KdTree(n)
    buff = {}
    k = 0

    for _ in range(q):
        com, u, v = [int(i) for i in input().split()]
        if com == 0:
            if u not in buff:
                k += 1
            buff[u] = v
        elif com == 1:
            if k > 0:
                for x, y in random.sample(buff.items(), k=k):
                    tree.insert(x, y)
                buff = {}
                k = 0
            print(tree.miny(u, v))
        else:
            raise ValueError('invalid command: {}'.format(com))


if __name__ == '__main__':
    run()

Submission status: Accepted

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

size = 1
while size < n :
    size *= 2
size = size * 2 - 1

seg_tree = [2**31 -1 for x in range(size)]

def update(i, x) :
    ind = size // 2 + i
    seg_tree[ind] = x
    
    while ind : 
        ind = (ind - 1) // 2
        ch1 = seg_tree[ind * 2 + 1]
        ch2 = seg_tree[ind * 2 + 2]
        seg_tree[ind] = min(ch1, ch2)
        
def find(s, t, k, l, r) :
    # no overlap
    if r < s or t < l :
        return 10 ** 20
    # total overlap
    if s <= l and r <= t :
        return seg_tree[k]
    # partial overlap
    else :
        vl = find(s, t, k * 2 + 1, l, (l + r) // 2)
        vr = find(s, t, k * 2 + 2, (l + r) // 2 + 1, r)
        
        return min(vl, vr)

for i in range(q) :
    com, x, y = map(int, input().split())
    
    if com == 0 :
        update(x, y)
    else :
        answer.append(find(x, y, 0, 0, size // 2))

for a in answer :
    print(a)

Submission status: Accepted

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

# max_num
INF = 2**31 - 1

# generate seg tree
seg_size = 2

while seg_size < n :
    seg_size *= 2
    
seg_size = seg_size * 2 - 1
seg_tree = [INF for x in range(seg_size)]

answer_stk = []

# update 
def update(i, x) :
    # leaf for index @ i
    idx = seg_size // 2 + i
    seg_tree[idx] = x
    
    while idx :
        idx = (idx - 1) // 2
        l_child = seg_tree[idx * 2 + 1]
        r_child = seg_tree[idx * 2 + 2]
        
        seg_tree[idx] = min(l_child, r_child)

# query
def query(s, t, l, r, curnode) :
    # no overlap then return INF
    if s > r or t < l :
        return INF
    
    # full overlap then return current node
    if s <= l and t >= r :
        return seg_tree[curnode]
    
    # partial overlap then return min for next
    else :
        l_child = curnode * 2 + 1
        r_child = curnode * 2 + 2
        
        l_value = query(s, t, l, (l + r) // 2, l_child)
        r_value = query(s, t, (l + r) // 2 + 1, r, r_child)
        
        return min(l_value, r_value)
    
# do main query
for i in range(q) :
    q, x, y = map(int, input().split())
    
    # update
    if q == 0 :
        update(x, y)
        
    # query 
    else :
        answer_stk.append(query(x, y, 0, seg_size // 2, 0))
        
for a in answer_stk :
    print(a)

Submission status: Accepted

Solution code:
import math
class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree", "default"]

    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.default = default
        self.init_tree()

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

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

        return result

    def set_value(self, i: int, value: int, op: str = "="):
        tree = self.tree
        k = self.elem_size + i
        if op == "=":
            tree[k] = value
        elif op == "+":
            tree[k] += value
        elif op == "?":
            # ===== change me =====
            tree[k] = value if value < tree[k] else tree[k]

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

import sys
n, q = map(int, input().split())
tree = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
append = ans.append
for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
    if com == 0:
        tree.set_value(x, y)
    else:
        append(tree.get_value(x, y+1))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import math
class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        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.default = default
        self.op = op
        self.init_tree()

    def init_tree(self) -> None:
        tree = self.tree
        for i in range(self.elem_size - 1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1) + 1]
            # ===== change me =====
            tree[i] = self.op(left, right)

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

        return result

    def set_value(self, i: int, value: int, op: str = "="):
        tree = self.tree
        k = self.elem_size + i
        if op == "=":
            tree[k] = value
        elif op == "+":
            tree[k] += value
        elif op == "?":
            # ===== change me =====
            tree[k] = value if value < tree[k] else tree[k]

        while k > 1:
            k >>= 1
            left, right = tree[k << 1], tree[(k << 1) + 1]
            # ===== change me =====
            tree[k] = self.op(left, right)

import sys
n, q = map(int, input().split())
tree = SegmentTree([2**31-1]*n, 2**31-1, min)
ans = []
append = ans.append
for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
    if com == 0:
        tree.set_value(x, y)
    else:
        append(tree.get_value(x, y+1))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import math
class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        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.default = default
        self.op = op
        self.init_tree(op)

    def init_tree(self, op) -> None:
        tree = self.tree
        for i in range(self.elem_size - 1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1) + 1]
            # ===== change me =====
            tree[i] = op(left, right)

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

        return result

    def set_value(self, i: int, value: int, op: str = "="):
        tree = self.tree
        k = self.elem_size + i
        if op == "=":
            tree[k] = value
        elif op == "+":
            tree[k] += value
        elif op == "?":
            # ===== change me =====
            tree[k] = value if value < tree[k] else tree[k]

        while k > 1:
            k >>= 1
            left, right = tree[k << 1], tree[(k << 1) + 1]
            # ===== change me =====
            tree[k] = self.op(left, right)

import sys
n, q = map(int, input().split())
tree = SegmentTree([2**31-1]*n, 2**31-1, min)
ans = []
append = ans.append
for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
    if com == 0:
        tree.set_value(x, y)
    else:
        append(tree.get_value(x, y+1))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import math
class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        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.default = default
        self.op = op
        self.init_tree(op)

    def init_tree(self, op) -> None:
        tree = self.tree
        for i in range(self.elem_size - 1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1) + 1]
            # ===== change me =====
            tree[i] = op(left, right)

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

        return result

    def set_value(self, i: int, value: int, op: str = "="):
        tree = self.tree
        k = self.elem_size + i
        if op == "=":
            tree[k] = value
        elif op == "+":
            tree[k] += value
        elif op == "?":
            # ===== change me =====
            tree[k] = value if value < tree[k] else tree[k]

        while k > 1:
            k >>= 1
            left, right = tree[k << 1], tree[(k << 1) + 1]
            # ===== change me =====
            tree[k] = self.op(left, right)

import sys
n, q = map(int, input().split())
tree = SegmentTree([2**31-1]*n, 2**31-1, min)
ans = []
append = ans.append
for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
    if com == 0:
        tree.set_value(x, y)
    else:
        append(tree.get_value(x, y+1))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import math
import sys

def make_tree(a: list, default: int, op):
    real_size = len(a)
    elem_size = 1 << math.ceil(math.log2(real_size))
    tree = [default] * elem_size + a + [default] * (elem_size - real_size)

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

    return tree

def get_min(tree: list, x: int, y: int):
    result, elem_size = float("inf"), len(tree)//2
    l, r = x + elem_size, y + elem_size

    while l < r:
        if l & 1:
            result = tree[l] if tree[l] < result else result
            l += 1
        if r & 1:
            r -= 1
            result = tree[r] if tree[r] < result else result
        l, r = l >> 1, r >> 1

    return result

def set_value(tree: list, i: int, value: int, op):
    k = len(tree)//2 + i
    tree[k] = value

    while k > 1:
        k >>= 1
        left, right = tree[k << 1], tree[(k << 1) + 1]
        tree[k] = op(left, right)

if __name__ == "__main__":
    n, q = map(int, input().split())
    tree = make_tree([2**31-1]*n, 2**31-1, min)
    ans = []
    append = ans.append
    for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
        if com == 0:
            set_value(tree, x, y, min)
        else:
            append(get_min(tree, x, y+1))
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import math
import sys

class SegmentTree(object):
    __slots__ = ["elem_size", "tree_size", "tree", "default", "op"]

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

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

    def get_value(self, x: int, y: 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):
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

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

if __name__ == "__main__":
    n, q = map(int, input().split())
    tree = SegmentTree([2**31-1]*n, 2**31-1, min)
    ans = []
    append = ans.append
    for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
        if com == 0:
            tree.set_value(x, y)
        else:
            append(tree.get_value(x, y+1))
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
#単体変更, 区間取得

class RMQ:
    #INF = int(1e18)
    INF = int((1<<31)-1)
    n = 0
    n_ = 0
    val = []
    def __init__(self, n_):
        n = 1
        while n < n_:
            n = n * 2
        self.n = n
        self.n_ = n_
        self.val = [self.INF] * (2 * n - 1)

    @staticmethod
    def merge(a, b):
        return min(a, b)
        
    def update(self,k, x):
        k = k + self.n - 1
        self.val[k] = x
        while k:
            k = (k-1)//2
            self.val[k] = self.merge(self.val[k*2+1], self.val[k*2+2])

    def dfs(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.INF
        if a <= l and r <= b:
            return self.val[k]
        vl = self.dfs(a, b, k * 2 + 1, l, (l+r)//2)
        vr = self.dfs(a, b, k * 2 + 2, (l+r)//2, r)
        return self.merge(vl, vr)
    

    def query(self, a, b):
        return self.dfs(a, b, 0, 0, self.n)

    
n, q = list(map(int, input().split()))
rmq = RMQ(n)

while q:
    q = q - 1
    com, x, y = list(map(int, input().split()))
    if com == 0:
        rmq.update(x, y)
    else:
        print (rmq.query(x, y + 1))

Submission status: Accepted

Solution code:
#単体変更, 区間取得

class RMQ:
    #INF = int(1e18)
    INF = int((1<<31)-1)
    n = 0
    n_ = 0
    val = []
    def __init__(self, n_):
        n = 1
        while n < n_:
            n = n * 2
        self.n = n
        self.n_ = n_
        self.val = [self.INF] * (2 * n - 1)

    @staticmethod
    def merge(a, b):
        return min(a, b)
        
    def update(self,k, x):
        k = k + self.n - 1
        self.val[k] = x
        while k:
            k = (k-1)//2
            self.val[k] = self.merge(self.val[k*2+1], self.val[k*2+2])

    def dfs(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.INF
        if a <= l and r <= b:
            return self.val[k]
        vl = self.dfs(a, b, k * 2 + 1, l, (l+r)//2)
        vr = self.dfs(a, b, k * 2 + 2, (l+r)//2, r)
        return self.merge(vl, vr)
    

    def query(self, a, b):
        return self.dfs(a, b, 0, 0, self.n)

    
n, q = list(map(int, input().split()))
rmq = RMQ(n)

query = rmq.query
update = rmq.update
while q:
    q = q - 1
    com, x, y = list(map(int, input().split()))
    if com == 0:
        update(x, y)
    else:
        print (query(x, y + 1))

Submission status: Accepted

Solution code:
import math
import sys

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default"]

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

        for i in range(elem_size - 1, 0, -1):
            l, r = tree[i<<1], tree[(i<<1)+1]
            tree[i] = l if l < r else r

    def get_value(self, x: int, y: int) -> int:
        l, r = x + self.elem_size, y + self.elem_size
        tree, result = self.tree, self.default
        while l < r:
            if l & 1:
                if tree[l] < result:
                    result = tree[l]
                l += 1
            if r & 1:
                r -= 1
                if tree[r] < result:
                    result = tree[r]
            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:
        tree = self.tree
        while i > 1:
            i >>= 1
            l, r = tree[i<<1], tree[(i<<1)+1]
            tree[i] = l if l < r else r
 
n, q = map(int, input().split())
tree = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
append = ans.append
for com, x, y in (map(int, l.split()) for l in sys.stdin.readlines()):
    if com == 0:
        tree.set_value(x, y)
    else:
        append(tree.get_value(x, y+1))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
class Segmenttree_min():
    def __init__(self,number):
        n=1
        inf=(1<<31)-1
        while n<number:
            n*=2
        self.n=n
        self.list=[inf]*(2*n-1)
    
    def add(self,i,x):#0indexed ith add x
        i+=self.n-1
        self.list[i]=x
        while i>0:
            i=(i-1)//2
            self.list[i]=min(self.list[2*i+1],self.list[2*i+2])
        
    def search(self,a,b,k,l,r):#call as search(a,b,0,0,self.n) minimun in [a,b)
        if r<=a or b<=l:
            return (1<<31)-1
        elif a<=l and r<=b:
            return self.list[k]
        else:
            vl=self.search(a,b,2*k+1,l,(l+r)//2)
            vr=self.search(a,b,2*k+2,(l+r)//2,r)
            return min(vl,vr)

N,Q=map(int,input().split())
ans=[]
tree=Segmenttree_min(N)
for i in range(Q):
    c,x,y=map(int,input().split())
    if c==0:
        tree.add(x,y)
    else:
        ans.append(tree.search(x,y+1,0,0,tree.n))
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
dat = [None] * 400000
m = 0

def init():
    global dat, m
    for i in range(2 * m - 1):
        dat[i] = 2 ** 31 - 1

def update(i, x):
    global dat, m
    i += m - 1
    dat[i] = x
    while i > 0:
        i = (i - 1) // 2
        dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2])

def query(a, b, k, l, r):
    global dat, m
    if r <= a or b <= l:
        return 2 ** 31 - 1
    if a <= l and r <= b:
        return dat[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = query(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)

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

while m < n:
    m *= 2

init()

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        print(query(x, y + 1, 0, 0, m))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class SegmentTree:
    def __init__(self, func, arr, default):
        self.func = func
        self.arr = arr
        self.default = default
        
        self.arrlen = len(self.arr)
        self.bitlen = (len(self.arr)-1).bit_length() + 1
        self.bottomlen = pow(2, self.bitlen-1)
        self.bottomst = pow(2, self.bitlen-1) - 1
        
        self.segtree = [self.default] * (2*self.bottomlen - 1)
        self.segtree[self.bottomst:self.bottomst+self.arrlen] = self.arr
        
        for idx in range(self.bottomst-1, -1, -1):
            self.segtree[idx] = self.func(self.segtree[2*idx+1],
                                          self.segtree[2*idx+2])
    
    # idx番目の値をxに変更(0-indexed)
    def update(self, idx:int, x:int):
        idx += self.bottomst
        self.segtree[idx] = x
        while idx > 0:
            idx = (idx-1)//2
            self.segtree[idx] = self.func(self.segtree[2*idx+1],
                                          self.segtree[2*idx+2])
        
    # [a,b) の値を取得(0-indexed)
    def query(self, a:int, b:int, idx:int, l:int, r:int):
        if r <= a or b <= l:
            return self.default
        
        elif a <= l and r <= b:
            return self.segtree[idx]
        
        else:
            return self.func(self.query(a,b, 2*idx+1, l, (l+r)//2),
                             self.query(a,b, 2*idx+2, (l+r)//2, r))

    # リセット
    def reset(self):
        self.segtree = [self.default] * (2*self.bottomlen - 1)
        self.segtree[self.bottomst:self.bottomst+self.arrlen] = self.arr
        
        for idx in range(self.bottomst-1, -1, -1):
            self.segtree[idx] = self.func(self.segtree[2*idx+1],
                                          self.segtree[2*idx+2])
            

n,q = li()
default = pow(2,31)-1
arr = [default]*n
segtree = SegmentTree(min, arr, default)
nbit = pow(2, (n-1).bit_length())

for _ in range(q):
    command, a, b = li()
    
    if command == 0:
        segtree.update(a,b)
    
    elif command == 1:
        print(segtree.query(a,b+1,0,0,nbit))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())

def init(N): #セグ木の初期化
    n = 1
    while n < N: n *= 2
    return n

def Update(i, x, n, L): #aiをxに変更する
    K = n - 1 + i
    L[K] = x
    while K > 0:
        K = (K - 1)//2
        L[K] = min(L[2 * K + 1], L[2 * K + 2])

def Find(s, t, k, l, r, L): #[s:t)の最小値を出力する
    if r <= s or t <= l: return 2**31-1
    elif s <= l and r <= t: return L[k]
    else:
        vl = Find(s, t, 2*k+1, l, (l+r)//2, L)
        vr = Find(s, t, 2*k+2, (l+r)//2, r, L)
        return min(vl, vr)

n = init(N)
SegTree = [2**31-1] * (2 * n - 1)
for i in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        Update(x, y, n, SegTree)
    elif com == 1:
        print(Find(x, y+1, 0, 0, n, SegTree))

Submission status: Accepted

Solution code:
import sys
import time
import math
sys.setrecursionlimit(20000)
def update(tree,x,y,N):
    # offset
    #x += int(N/2)
    x += N - 1
    tree[x] = y
    # segment tree no update suru
    while True:
        if(x <= 0):
            break
        x = math.floor((x - 1)/2)
        left = x*2+1
        right = x*2+2
        tree[x] = min(tree[left],tree[right])

def find(tree,x,y,k,l,r):

    if (r <= x or y <= l):
        return 2**31 - 1
    # sita wo mite itte mitukatta toki (intersect)
    if ( x <= l and r <= y):
        return tree[k]
    # sita ni sagaru
    v_left = find(tree, x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(tree, x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    INT_MAX = 2**31 - 1
    N = 1
    while True:
        if(N >= _N):
            break
        N *= 2
    #N = 2*N - 1 - 1
    if not (N == 1):
        A_bin_tree = [INT_MAX]*(2*N - 1)
    else:
        A_bin_tree = [INT_MAX]
    #start = time.time()
    for i in range(query_num):
        operate,x,y = map(int, input().split())
        # update
        if(operate==0):
            update(A_bin_tree,x,y,N)
            #print(A_bin_tree)
        # find
        if(operate==1):
            # tyouten kara miteiku
            z = find(A_bin_tree,x,y+1,0,0,N)
            print(z)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Accepted

Solution code:
import sys

INF = 2**31 - 1


class RMQ:

    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp *= 2
        self.n = tmp * 2 - 1
        self.A = [INF] * (2 * self.n - 1)

    def update(self, i, x):
        i = self.n // 2 + i
        self.A[i] = x
        while i:
            i = (i - 1) // 2
            self.A[i] = min(self.A[i * 2 + 1], self.A[i * 2 + 2])

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


line = sys.stdin.readline()
n, q = map(int, line.split())
t = RMQ(n)
for i in range(q):
    line = sys.stdin.readline()
    com, x, y = map(int, line.split())
    if com == 0:
        t.update(x, y)
    else:
        print(t.find(x, y, 0, 0, t.n // 2))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
n, q = map(int, readline().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, readline().split())
    if t:
        ans.append(str(query(x, y+1)))
    else:
        update(x, y)
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, n, inf=float('inf')):
        #self.n = 2**(n-1).bit_length()
        _n = 1
        while _n < n:
            _n *= 2
        self.n = _n
        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)))