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 SegT():
    # originは初期データがあれば渡す
    def __init__(self, size, origin=None):
        self.size = 1
        while self.size < size: self.size *= 2
        self._data_init()
        if origin:
            for i in range(size):
                self.data[i+self.size-1] = origin[i]
            for i in range(self.size-2,-1,-1):
                self.data[i] = self.data[i*2+1] | self.data[i*2+2]

    def _data_init(self):
        self.e = pow(2, 31)-1 # 単位元
        self.data = [self.e for _ in range(self.size * 2 - 1)]

    def _calc(self, a, b):
        # ここは独自実装する
        return min(a, b)
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self._calc(self.data[i*2+1], self.data[i*2+2])
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return self.e
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return self._calc(vl, vr)

N, Q = map(int, input().split())
origin = [pow(2, 31) - 1 for i in range(N)]
segt = SegT(N)

for i in range(Q):
    t, l, r = input().split()
    if t == "0":
        segt.update(int(l), int(r))
    else:
        x = segt.get(int(l),int(r)+1)
        print(x)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
A = [2**31-1 for _ in range(n)]

class SegTree:
    def __init__(self, raw_data):
        n = len(raw_data)
        self.size = 1 << (n.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)

    def build(self, raw_data):
        for i, x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1, 0, -1):
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x < y else y # ここを変更
    
    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x < y else y # ここを変更
            i >>= 1
    
    def get_data(self, i):
        return self.data[i+self.size]
    
    # これを変更
    def get_max(self, L, R):
        L += self.size
        R += self.size + 1
        res = float("inf") # ここを変更
        while L < R:
            if L & 1:
                x = self.data[L]
                if res > x: res = x # ここを変更
                L += 1
            if R & 1:
                R -= 1
                x = self.data[R]
                if res > x: res = x # ここを変更
            L >>= 1
            R >>= 1
        return res

seg = SegTree(A)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        seg.update(x, y)
    else:
        print(seg.get_max(x, y))

Submission status: Accepted

Solution code:

class segment_tree:
    n = 0
    segtree = []
    max_v = 10**10

    def __init__(self, A, max_n=2**31 - 1):
        self.N = len(A)
        self.max_v = max_n
        self.n = (self.N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [max_n]*(2*self.n)
        for i in range(self.N):
            self.segtree[self.n+i - 1] = A[i]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = min(self.segtree[i*2 + 1], self.segtree[i*2 + 2])

    def update(self, i, x):
        id = self.n+i - 1
        self.segtree[id] = x
        while(id > 0):
            id = (id - 1) // 2
            self.segtree[id] = min(
                self.segtree[id*2 + 1], self.segtree[id*2+2])
            #print(self.segtree[id*2 + 1], self.segtree[id*2+2])


    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(self.max_v)
        if a <= l and r <= b:
            return(self.segtree[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))


n, q = map(int, input().split())
N = (n-1).bit_length()
N = 2 ** N
A = [2**31 - 1]*n
G = segment_tree(A)
for _ in range(q):
    a, x, y = map(int, input().split())
    if a == 0:
        G.update(x, y)
    else:
        y += 1
        print(G.query(x, y, 0, 0, N))

Submission status: Accepted

Solution code:
# セグメント木　verify
class SegTree():
    def __init__(self,N,function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)

        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
N,Q=map(int,input().split())
que=[tuple(map(int,input().split())) for i in range(Q)]
Seg=SegTree(N,min,2**31-1)
for index,u,v in que:
    if index==0:
        Seg.update(u,v)
    else:
        print(Seg.query(u,v+1))

Submission status: Accepted

Solution code:
class Segment:
    def __init__(self, N, init_val):
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.dat = [identity_element]*(2*self.N0)
        # 値を代入
        for i in range(N):
            self.dat[i+self.N0-1]=init_val[i]    
        # 構築
        for i in range(self.N0-2,-1,-1) :
            self.dat[i]=segfunc(self.dat[2*i+1],self.dat[2*i+2]) 

    # k番目の要素の値をxに変更
    def update(self, k, x):
        k += self.N0-1
        self.dat[k] = x
        while k >= 0:
            k = (k-1)//2
            self.dat[k] = segfunc(self.dat[2*k+1], self.dat[2*k+2])

    # 区間[l, r)の最小値を求める
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = identity_element
        # 区間を列挙しながら最小値を求める
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.dat[R-1])
            if L & 1:
                s = segfunc(s, self.dat[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
def segfunc(x,y):
    return min(x,y)
identity_element = 2**31-1

n,q = map(int,input().split())
seg = Segment(n,[identity_element]*n)

for i in range(q):
    c,x,y=map(int,input().split())
    if c:
        print(seg.query(x,y+1))
    else:
        seg.update(x,y)

Submission status: Accepted

Solution code:
from sys import stdin


class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


n,q   = [int(x) for x in stdin.readline().rstrip().split()]

lamb_min = lambda x,y : min(x,y)
seg = SegmentTree(n,lamb_min,2147483647)
for _ in range(q):
    c,x,y = [int(x) for x in stdin.readline().rstrip().split()]
    if c == 0:
        seg.update(x,y)
    elif c == 1:
        print(seg.query(x,y+1))

Submission status: Accepted

Solution code:
import sys,math
INF = 2**31-1
N,Q = map(int,sys.stdin.readline().split())
COM = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param
i = 1
while i < N:
    i*=2
N = i
MAX_N = 1 << math.ceil(math.log2(N)) #17
SEG = [INF]*(2*MAX_N-1)

def update(k,a):#0 indexed
    k += N-1
    SEG[k] = a
    while k > 0:
        k = (k-1)//2
        SEG[k] = min(SEG[k*2+1],SEG[k*2+2])

def find(a,b,i=0,l=0,r=N):#0 indexed
    if r <= a or  b <= l:
        return INF
    if a <= l and r <= b:
        return SEG[i]
    vl = find(a,b,2*i+1,l,(r+l)//2)
    vr = find(a,b,2*i+2,(r+l)//2,r)
    return min(vl,vr)

for com,x,y in COM:
    if com == 0:
        update(x,y)
    else:
        print(find(x,y+1))

Submission status: Accepted

Solution code:
class segtree:

    def __init__(self, n, operator, identity):
        """
        n:データ配列のサイズ
        operator:演算子(モノイド)。関数オブジェクト 最小=min, 最大=max
        identity:演算子に対応する単位元
        """
        nb = bin(n)[2:] #２進数に変換して先頭の0bを取り除く
        bc = sum([int(digit) for digit in nb]) #bitで1が立ってる数。これが1のときはちょうど2^nb.そうじゃないときは、2^nb<n<2^(nb+1)
        if bc == 1: #2^nbなら
            self.num_end_leaves = 2**(len(nb)-1) #最下段の葉っぱは2^nb個
        else:#そうじゃないなら2^(nb+1)確保
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #単位元で初期化

        self.identity = identity 
        self.operator = operator
        #後で使うので単位元と演算子を持っておく

    def update(self,x,val):
        """
        x:代入場所
        val:代入する値
        """
        actual_x = x+self.num_end_leaves #1-indexの末端の葉のindexがどこから始まるか分を足す(例えばデータ配列サイズ4のとき木配列サイズは8で、後半部はindex4から始まる。
        self.array[actual_x] = val #値を更新する
        while actual_x > 0 :
            actual_x = actual_x//2#親を見る
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#あたらしい子をつかって親を更新

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_left：クエリ区間の左
        q_right:クエリ区間の右
        arr_ind:木配列のインデックス。最初は親なので1
        leaf_left:木配列インデックスに対して、それが表す葉がカバーする範囲の左
        depth:木配列での深さ。カバー範囲の広さの計算に使用
        """
        width_of_floor = self.num_end_leaves//(2**depth) #今の葉のカバー幅
        leaf_right = leaf_left+width_of_floor-1 #左端とカバー幅から今の葉のカバー範囲の右を求める。

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #クエリ領域と葉が関係ないなら単位元を返す

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #クエリ領域に葉がすっぽり入ってるなら、葉の値を返す

        else: #そうじゃないならば、子を見る
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#子の左
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#子の右
            return self.operator(val_l,val_r)#子をマージする演算をする。

N, Q = map(int,input().split())

s_tree = segtree(N,min,2**31-1) #10**5までの配列なので適当に単位元は10**9
arr = [2**31-1] * N

#print(arr)

for i,a in enumerate(arr):
    s_tree.update(i,a)

for i in range(Q):
    a, x, y = map(int,input().split())
    if a == 0:
        s_tree.update(x,y)
    else:
        print(s_tree.get(x,y))

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:
from typing import Callable, Sequence, Union, List


class SegmentTree:
    __slots__ = ["default_value", "seg_func", "size", "tree"]

    def __init__(
        self,
        initial_values: Sequence,
        default_value: Union[int, str],
        seg_func: Callable,
    ) -> None:
        self.default_value = default_value
        self.seg_func = seg_func
        self.size = 1 << (len(initial_values) - 1).bit_length()
        self.tree = self._build(initial_values)

    def _build(self, initial_values) -> List:
        tree = [self.default_value] * (2 * self.size)

        for idx, val in enumerate(initial_values):  # set
            # modify val if needed (e.g. str -> ord())
            tree[idx + self.size - 1] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = self.seg_func(tree[2 * idx + 1], tree[2 * idx + 2])
        return tree

    def update(self, idx: int, val: int) -> None:
        idx += self.size - 1
        # modify val if needed as same as in _build()
        self.tree[idx] = val
        while idx:
            idx = (idx - 1) // 2
            x, y = 2 * idx + 1, 2 * idx + 2
            self.tree[idx] = self.seg_func(self.tree[x], self.tree[y])

    def query(self, left: int, right: int) -> Union[int, str]:
        if left > right:  # corner case
            return self.default_value

        left += self.size
        right += self.size
        result = self.default_value
        while left < right:
            if left & 1:
                result = self.seg_func(result, self.tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self.seg_func(result, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    N, Q = map(int, input().split())
    tree = SegmentTree([2 ** 31 - 1] * N, 2 ** 31 - 1, min)
    ans = []
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com:
            ans.append(tree.query(x, y + 1))
        else:
            tree.update(x, y)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
INF = 2**31 - 1

k = 1
while k < n:
    k *= 2

A = [-1] * (k-1) + [2**31-1] * k


def min_query(a, b, k, l, r):
    if r <= a or b <= l:
        ans = INF
    elif a <= l and r <= b:
        ans = A[k]
    else:
        c1 = min_query(a, b, 2*k+1, l, (l+r)//2)
        c2 = min_query(a, b, 2*k+2, (l+r)//2, r)
        ans = min(c1, c2)
    return ans


for i in range(k-2, -1, -1):
    A[i] = min(A[2*i+1], A[2*i+2])

for i in range(q):
    com, x, y = map(int, input().split())

    if com == 0:
        cur = k-1+x
        A[cur] = y
        while cur > 0:
            cur = (cur-1) // 2
            A[cur] = min(A[2*cur+1], A[2*cur+2])
    else:
        print(min_query(x, y+1, 0, 0, k))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
#Range Minimum Query
seg=[]
cnt=-1
inf=2**31-1
while 2**cnt<=n:
	cnt+=1
	seg.append([inf for _ in range(2**cnt)])

def f(i,j):
	Range=(2**(cnt-i)*j,2**(cnt-i)*(j+1)-1)
	if Range[0]>y or Range[1]<x:
		return inf
	elif Range[0]>=x and Range[1]<=y:
		return seg[i][j]
	else:
		return min(f(i+1,2*j),f(i+1,2*j+1))
for _ in range(q):
	c,x,y=map(int,input().split())
	if c==0:
		seg[-1][x]=y
		x//=2
		for j in range(1,cnt+1):
			seg[-j-1][x]=min(seg[-j][x*2],seg[-j][x*2+1])
			x//=2
	else:
		print(f(0,0))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class ABSsegtree: # 必要な配列の長さN,単位元ie,関数(2項演算)func,を渡す    
    def __init__(self,N,ie,func):
        self.func=func
        self.getLEN=1 # Length of list
        while self.getLEN<N:
            self.getLEN*=2
        self.getsize=self.getLEN*2 # =len(ST)
        self.getLIN=self.getsize-self.getLEN # internal nodes without ST[0]
        self.ST=[ie]*self.getsize

    def update(self,i,x): # i(0-index)にxをいれる
        i+=self.getLIN
        self.ST[i]=x
        while i>1:
            i//=2
            self.ST[i]=self.func(self.ST[2*i],self.ST[2*i+1])
    
    def get_interval(self,a,b): # [a,b)での最小値を求めたい
        a+=self.getLIN
        b+=self.getLIN
        ret=self.func(self.ST[a],self.ST[b-1])
        while a+1<b: # 階層ごとに見る
            if a%2==1:
                ret=self.func(self.ST[a],ret)
                a+=1
            a//=2
            if b%2==1:
                ret=self.func(self.ST[b-1],ret)
            b//=2
        if a==b:
            pass
        else:
            ret=self.func(ret,self.ST[a])
        return ret

N,Q=map(int,input().split())
ins=ABSsegtree(N,pow(2,31)-1,min)
for _ in range(Q):
    P,X,Y=map(int,input().split())
    if P==0:
        ins.update(X,Y)
    else:
        print(ins.get_interval(X,Y+1))

Submission status: Accepted

Solution code:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

# a = [14, 5, 9, 13, 7, 12, 11, 1, 7, 8]

# def segfunc(x, y):
#     return min(x, y)

# ide_ele = float('inf')

# seg = SegTree(a, segfunc, ide_ele)

# [0, 8)の最小値を表示
# print(seg.query(0, 8))
# 1

# 5番目を0に変更
# seg.update(5, 0)

# [0, 8)の最小値を表示
# print(seg.query(0, 8))
# 0

n,q = map(int,input().split())
cxy = [ list(map(int,input().split())) for _ in range(q) ]

INF = float("inf")

#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = INF
#################

a = [2**31-1]*n

seg = SegTree(a,segfunc,ide_ele)

for i in range(q):
    c = cxy[i][0]
    x = cxy[i][1]
    y = cxy[i][2]
    if c==0:
        seg.update(x,y)
    elif c==1:
        print(seg.query(x,y+1))
    else:
        print("Error")

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

class SegmentTree():
    def __init__(self,array,func,unit):
        self.N = len(array)
        self.f = func
        self.unit = unit
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)

def main():
    n,q = map(int,input().split())
    st = SegmentTree([(1<<31) - 1]*n,min,1<<32)

    for _ in range(q):
        query = list(map(int,input().split()))
        if query[0] == 0:
            i = query[1]
            x = query[2]
            st.update(i,x)
        else:
            s = query[1]
            t = query[2]
            print(st.query(s,t + 1))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SegmentTree:
    n=0
    node=[]

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


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

    def getmin(self, a, b, k=0, l=0, r=-1):
        if r<0: r = self.n
        if a<=l and r<=b: return self.node[k]
        if r<=a or  b<=l: return INF
        
        vl = self.getmin(a, b, 2*k+1, l, int((l+r)/2))
        vr = self.getmin(a, b, 2*k+2, int((l+r)/2), r)
        return min(vl, vr)


INF = 2**31-1
sz, q = map(int, input().split())
rmq = SegmentTree(sz)
for _ in range(q):
    c, x, y = map(int, input().split())
    if c: print(rmq.getmin(x, y+1))
    else: rmq.update(x, y)

Submission status: Accepted

Solution code:
INF = 10 ** 20

n, q = map(int, input().split())
n_t = 1
seg_tree = []


def initRMQ(n):
    global n_t
    while n_t < n:
        n_t *= 2
    for i in range(0, 2*n_t - 1):
        seg_tree.append(2 ** 31 - 1)


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


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


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


initRMQ(n)
for _ in range(q):
    com, x, y = map(int, input().split())
    if not com:
        update(x, y)
    else:
        print(findMin(x, y))

Submission status: Accepted

Solution code:
import math

class RMQ:
    INF = 2**31 - 1
    N = 0
    def __init__(self, n_):
        self.N = 1
        RMQ.D = []
        while self.N < n_:
            self.N = 2 * self.N

        for i in range((2*self.N)-1):
             RMQ.D.append(RMQ.INF)

    def update(self, k, x):
        k += self.N-1
        RMQ.D[k] = x
        while k > 0:
            k = math.floor((k-1)/2)
            RMQ.D[k] = min(RMQ.D[(k*2)+1], RMQ.D[(k*2)+2])

    def findMin(self, a, b):
        return self.query(a, b+1, 0, 0, self.N)

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return RMQ.INF
        if a <= l and r <= b:
            return RMQ.D[k]

        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)


if __name__ == "__main__":
    n_, q = (int(z) for z in input().split()) #n: num of sequence, q: num of query
    rmq = RMQ(n_)

    for i in range(q):
        com, x, y = (int(z) for z in input().split())

        if(com == 0):
            rmq.update(x, y)
        else:
            res = rmq.findMin(x, y)
            print(res)

Submission status: Accepted

Solution code:

class SegmentTree:
    def __init__(self, n, f, gen):
        self.n = n
        self.size = 1
        self.gen = gen
        self.f = f
        while self.size < n:
            self.size *= 2
        self.seg = [gen] * (2 * self.size)

    def set(k, x):
        self.seg[k + self.size] = x

    def build(self):
        k = self.size - 1
        while k>0:
            self.seg[k] = self.f(self.seg[2 * k], self.seg[2 * k + 1])
            k -= 1

    def update(self, i, x):
        k = i + self.size
        self.seg[k] = x
        while k > 0:
            k >>= 1
            self.seg[k] = self.f(self.seg[2 * k], self.seg[2 * k + 1])
    
    def query(self, a, b):
        """
        [a,b)
        """
        L = self.gen
        R = self.gen
        A = a + self.size
        B = b + self.size
        while A<B:
            if A%2:
                L = self.f(L, self.seg[A])
                A += 1
            if B%2:
                B -= 1
                R = self.f(self.seg[B], R)
            A >>= 1
            B >>= 1
        return f(L, R)
    


def f(a, b):
    return min(a,b)

def main():
    n, q = map(int, input().split())
    seg = SegmentTree(n, f, 2**31-1)
    seg.build()

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#単位元を設定
ide = float('inf')

class SegmentTree:
	def __init__(self,n):
        #セグ木の頂点はindex == 1から。index == 0は無視すること。
        #つまり、STtable[0]は無視。頂点はSTtable[1]。
		self.n = n
		tmp = 0
		while True:
			if 2 ** tmp >= self.n:
				break
			tmp += 1
		self.STtable = [ide] * (2*2**tmp)
		self.STtable_size = len(self.STtable)

	def update(self,i,a):
        #更新のためのインデックスの指定は0_indexedで。
		i += self.STtable_size//2
		self.STtable[i] = a
		while i > 0:
			i //= 2
			self.STtable[i] = min(self.STtable[i*2], self.STtable[i*2+1])

	def find(self,a,b,k=1,l=0,r=None):
        #kは頂点番号。初期値は1にすること。
		#[a,b)の最小を返す。
		#[l,r)からです。
        #初期値のrは、self.STtable_size//2にすると、ちょうど要素数と同じ値になって[l,r)のrになる。
		if r == None:
			r = self.STtable_size//2        
		if a >= r or b <= l:
			return ide
		elif a <= l and b >= r:
			return self.STtable[k]
		else:
			v1 = self.find(a,b,2*k,l,(l+r)/2)
			v2 = self.find(a,b,2*k+1,(l+r)/2,r)
			return min(v1,v2)

n,q = map(int, input().split())
solve = SegmentTree(n)
ans = []
for _ in range(q):
    cond, x, y = map(int, input().split())
    if cond == 0:
        solve.update(x,y)
    else:
        ans.append(solve.find(x,y+1))

for a in ans:
    if a == ide:
        print(2147483647)
    else:
        print(a)

Submission status: Accepted

Solution code:
class SegTreeNode:
    def __init__(self, value = 0, l = 0, r = 0, lson = None, rson = None):
        self.value = value
        self.l = l
        self.r = r
        self.lson = lson
        self.rson = rson

class SegTree:
    MIN_NUMBER = 0
    MAX_NUMBER = 2**31 - 1
    def __init__(self, l, r):
        self.root = self.build(l, r)
    
    def build(self, l, r):
        if l > r:
            return None
        root = SegTreeNode(self.MAX_NUMBER, l, r)
        if l == r:
            return root
        mid = (l + r) >> 1
        root.lson = self.build(l, mid)
        root.rson = self.build(mid+1, r)
        return root
    
    def __update(self, root, l, r, value):
        if l > root.r or r < root.l or root == None:
            return
        if l <= root.l and root.r <= r:
            root.value = value
            return
        self.__update(root.lson, l, r, value)
        self.__update(root.rson, l, r, value)
        root.value = min(root.lson.value, root.rson.value)
    
    def update(self, i, value):
        self.__update(self.root, i, i, value)

    def __query(self, root, l, r):
        if l > root.r or r < root.l or root == None:
            return SegTree.MAX_NUMBER
        if l <= root.l and root.r <= r:
            return root.value
        return min(self.__query(root.lson, l, r), self.__query(root.rson, l, r))

    def query(self, l, r):
        return self.__query(self.root, l, r)

n, q = map(int, input().split())
seg = SegTree(0, n)
while q:
    q -= 1
    op, l, r = map(int, input().split())
    if op == 0:
        seg.update(l, r)
    else:
        print(seg.query(l, r))

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = 2 ** 31 -1
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])
    
    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n, q = [int(x) for x in input().split()]

seg = SegTree([2**31 - 1] * n, segfunc, ide_ele)

for _ in range(q):
    c, x, y = [int(x) for x in input().split()]
    if c == 0:
        seg.update(x, y)
    else:
        print(seg.query(x, y + 1))