Problem:
 Score : 100 points    Problem Statement You are given an array a_0, a_1, ..., a_{N-1} of length N . Process Q queries of the following types.  The type of i -th query is represented by T_i .   T_i=1 : You are given two integers X_i,V_i . Replace the value of A_{X_i} with V_i .  T_i=2 : You are given two integers L_i,R_i . Calculate the maximum value among A_{L_i},A_{L_i+1},\cdots,A_{R_i} .  T_i=3 : You are given two integers X_i,V_i . Calculate the minimum j such that X_i \leq j \leq N, V_i \leq A_j . If there is no such j , answer j=N+1 instead.       Constraints  1 \leq N \leq 2 \times 10^5  0 \leq A_i \leq 10^9  1 \leq Q \leq 2 \times 10^5  1 \leq T_i \leq 3  1 \leq X_i \leq N , 0 \leq V_i \leq 10^9 ( T_i=1,3 )  1 \leq L_i \leq R_i \leq N ( T_i=2 )  All values in Input are integer.         Input Input is given from Standard Input in the following format:  N  Q  A_1  A_2  \cdots  A_N First query
Second query \vdots  Q -th query  Each query is given in the following format:  If T_i=1,3 ,  T_i  X_i  V_i   If T_i=2 ,  T_i  L_i  R_i       Output For each query with T_i=2, 3 , print the answer.        Sample Input 1 5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3      Sample Output 1 3
3
2
6   First query: Print 3 , which is the maximum of (A_1,A_2,A_3,A_4,A_5)=(1,2,3,2,1) .  Second query: Since 3>A_2 , j=2 does not satisfy the condition．Since 3 \leq A_3 , print j=3 .  Third query: Replace the value of A_3 with 1 . It becomes A=(1,2,1,2,1) .  Fourth query: Print 2 , which is the maximum of (A_2,A_3,A_4)=(2,1,2) .  Fifth query: Since there is no j that satisfies the condition, print j=N+1=6 .

Solution (Python):
class SegmentTree:
    def __init__(self, n, func=lambda x, y : max(x, y), default_val = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [default_val] * self.node_n
        self.default_val = default_val
        self.f = func

        if init_list:
            self.tree[self.offset:self.offset+n] = init_list
            self.update_all()
    
    def set_values(self, val_list):
        n = len(val_list)
        assert self.leaf_n >= n
        self.tree[self.offset:self.offset+n] = val_list
    
    def set_value(self, index, val):
        assert 0 <= index < self.leaf_n
        self.tree[self.offset+index] = val

    def get_value(self, index):
        assert 0 <= index < self.leaf_n
        return self.tree[self.offset + index]

    def update_all(self):
        l = self.offset
        n = self.leaf_n
        while l > 0:
            for i in range(l, l + n, 2):
                self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            l >>= 1
            n >>= 1

    def update(self, index, val):
        assert 0 <= index < self.leaf_n
        i = self.offset + index
        self.tree[i] = val
        while i > 0:
            if i & 1 == 0:
                i -= 1
            self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            i >>= 1
    
    def query(self, l, r):
        assert 0 <= l <= r < self.leaf_n
        left_val = self.default_val
        right_val = self.default_val
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.default_val))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.default_val
        while True:
            while i & 1 != 0: 
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1

    def search_min_left(self, r, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の l を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x): x <= v
        '''
        assert(0 <= r < self.leaf_n and check_func(self.default_val))
        i = r + self.offset
        if not check_func(self.tree[i]):
            return -1
        right_val = self.default_val
        while True:
            while i & 1 == 0 and i > 0: 
                i = (i - 1) >> 1
            x = self.f(self.tree[i], right_val)
            if not check_func(x):
                while i < self.offset:
                    i = (i + 1) << 1 
                    x = self.f(self.tree[i], right_val)
                    if check_func(x):
                        right_val = x
                        i -= 1
                return i - self.offset + 1
            right_val = x
            if i & (i + 1) == 0:
                return 0
            i -= 1

n, q = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()

st = SegmentTree(n, max, 0, a)
ans = []
for _ in range(q):
    t, x, v = map(int, input().split())
    if t == 1:
        st.update(n-x, v)
    elif t == 2:
        ans.append(st.query(n-v, n-x))
    else:
        if v == 0:
            ans.append(x)
        else:
            i = st.search_min_left(n - x, lambda y: y < v)
            if i < 0:
                ans.append(x)
            else:
                ans.append(n - i + 1)
for x in ans:
    print(x)

Solution (Python):
class SegmentTree:
    def __init__(self, n, func=lambda x, y : max(x, y), default_val = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [default_val] * self.node_n
        self.default_val = default_val
        self.f = func

        if init_list:
            self.tree[self.offset:self.offset+n] = init_list
            self.update_all()
    
    def set_values(self, val_list):
        n = len(val_list)
        assert self.leaf_n >= n
        self.tree[self.offset:self.offset+n] = val_list
    
    def set_value(self, index, val):
        assert 0 <= index < self.leaf_n
        self.tree[self.offset+index] = val

    def get_value(self, index):
        assert 0 <= index < self.leaf_n
        return self.tree[self.offset + index]

    def update_all(self):
        l = self.offset
        n = self.leaf_n
        while l > 0:
            for i in range(l, l + n, 2):
                self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            l >>= 1
            n >>= 1

    def update(self, index, val):
        assert 0 <= index < self.leaf_n
        i = self.offset + index
        self.tree[i] = val
        while i > 0:
            if i & 1 == 0:
                i -= 1
            self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            i >>= 1
    
    def query(self, l, r):
        assert 0 <= l <= r < self.leaf_n
        left_val = self.default_val
        right_val = self.default_val
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.default_val))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.default_val
        while True:
            while i & 1 != 0: 
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1

    def search_min_left(self, r, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の l を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x): x <= v
        '''
        assert(0 <= r < self.leaf_n and check_func(self.default_val))
        i = r + self.offset
        if not check_func(self.tree[i]):
            return -1
        right_val = self.default_val
        while True:
            while i & 1 == 0 and i > 0: 
                i = (i - 1) >> 1
            x = self.f(self.tree[i], right_val)
            if not check_func(x):
                while i < self.offset:
                    i = (i + 1) << 1 
                    x = self.f(self.tree[i], right_val)
                    if check_func(x):
                        right_val = x
                        i -= 1
                return i - self.offset + 1
            right_val = x
            if i & (i + 1) == 0:
                return 0
            i -= 1

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

st = SegmentTree(n, max, 0, a)
ans = []
for _ in range(q):
    t, x, v = map(int, input().split())
    if t == 1:
        st.update(x-1, v)
    elif t == 2:
        ans.append(st.query(x-1, v-1))
    else:
        if v == 0:
            ans.append(x)
        else:
            i = st.search_max_right(x - 1, lambda y: y < v)
            ans.append(x if i < 0 else i + 2)
for x in ans:
    print(x)

Solution (Python):
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ng = x
        ok = n+1
        while ok - ng > 1:
            mid = (ok+ng)//2
            if seg.fold(x, mid) >= v:
                ok = mid
            else:
                ng = mid
        print(ok)

Solution (Python):
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ng = x
        ok = n+1
        while ok - ng > 1:
            mid = (ok+ng)//2
            if seg.fold(x, mid) >= v:
                ok = mid
            else:
                ng = mid
        print(ok)

Solution (Python):
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ng = x
        ok = n+1
        while ok - ng > 1:
            mid = (ok+ng)//2
            if seg.fold(x, mid) >= v:
                ok = mid
            else:
                ng = mid
        print(ok)

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$}SA&2Hm15WWY<I}lj3krE|{7kgL)ac-Mq_tINx2(m=mglS4k%ig571ikgvK0t5np+H~Cmp;bMkQ7CcRDM=4V3EW5`{v__d`HTMc2$cjGOu@{+LkL?uBW
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
A = list(map(int,input().split()))
qs = [tuple(map(int,input().split())) for i in range(Q)]

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

INF = float('inf')
segt = SegTree(A, lambda x,y:max(x,y), -INF)

ans = []
for a,b,c in qs:
    if a==1:
        segt.update(b-1,c)
    elif a==2:
        ans.append(segt.query(b-1,c))
    else:
        l = b-1
        r = N
        if segt.query(l,r) < c:
            ans.append(N+1)
        else:
            while r-l > 1:
                m = (l+r)//2
                if segt.query(l,m) >= c:
                    r = m
                else:
                    l = m
            ans.append(r)
print(*ans, sep='\n')

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$}SA&2Hm15WWY<I}li`BRO&q?=i4*+Z?->-cm!5CE6BDQwk+}lim{a)?51ky|sq|eJNl17@Z+0i6SY-DPceshx7N%
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [ide_ele]*(2*self.N0)
            
        def update(self, k, x):
            k += self.N0
            self.data[k] = x
            while k > 0 :
                k = k >> 1
                self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
        
        def query(self, l, r):
            L, R = l+self.N0, r+self.N0
            s = self.ide_ele
            while L < R:
                if R & 1:
                    R -= 1
                    s = self.segf(s, self.data[R])
                if L & 1:
                    s = self.segf(s, self.data[L])
                    L += 1
                L >>= 1
                R >>= 1
            return s
        
        def binsearch(self, l, r, check, reverse = False):
            L, R = l+self.N0, r+self.N0
            SL, SR = [], []
            while L < R:
                if R & 1:
                    R -= 1
                    SR.append(R)
                if L & 1:
                    SL.append(L)
                    L += 1
                L >>= 1
                R >>= 1
            
            if reverse:
                pre = self.ide_ele
                for idx in (SR + SL[::-1]):
                    if check(self.segf(self.data[idx], pre)):
                        break
                    else:
                        pre = self.segf(self.data[idx], pre)
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(self.data[2*idx+1], pre)):
                        idx = 2*idx + 1
                    else:
                        pre = self.segf(self.data[2*idx+1], pre)
                        idx = 2*idx
                return idx - self.N0
            else:
                pre = self.ide_ele
                for idx in (SL + SR[::-1]):
                    if not check(self.segf(pre, self.data[idx])):
                        pre = self.segf(pre, self.data[idx])
                    else:
                        break
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(pre, self.data[2*idx])):
                        idx = 2*idx
                    else:
                        pre = self.segf(pre, self.data[2*idx])
                        idx = 2*idx + 1
                return idx - self.N0
    N,Q=MI()
    A=LI()
    seg=Segtree(A,0,segf=max)
    N0=seg.N0
    for _ in range(Q):
        t,x,v=MI()
        if t==1:
            x-=1
            seg.update(x,v)
        elif t==2:
            l=x-1
            r=v
            print(seg.query(l,r))
        else:
            l=x-1
            r=N
            ans=seg.binsearch(l,r,lambda x: x>=v)
            if ans==None:
                ans=N
            
                
            print(ans+1)
    
    

 
 


        
    





main()

Solution (Python):

class segmentTree:
    def __init__(self, init_val, operator, identity):
        """
        :param init_val: 操作したい配列
        :param operator: 演算子(minはそのままでok。sumはlistを引数にとるからエラー->add関数を自作)
        :param identity: 演算子に対応する単位元(minならinf,sumなら0)
        """
        self.identity = identity
        self.operator = operator

        n = len(init_val)
        n_bin = bin(n)[2:]
        bc = sum([int(digit) for digit in n_bin])
        if bc == 1:  
            self.num_end_leaves = 2**(len(n_bin)-1)
        else:  
            self.num_end_leaves = 2**len(n_bin)

        self.tree = [identity for _ in range(self.num_end_leaves * 2)]
        
        for i in range(n):
            self.tree[i + self.num_end_leaves] = init_val[i]
        
        for i in range(1, self.num_end_leaves)[::-1]:
            self.tree[i] = self.operator(self.tree[2*i], self.tree[2*i+1])


    def update(self, x, val):
        """
        :param x: 更新するidx(0-indexed)
        :param val: 更新する値
        """
        leaf_x = x + self.num_end_leaves
        self.tree[leaf_x] = val
        while leaf_x > 0:
            leaf_x //= 2
            self.tree[leaf_x] = self.operator(self.tree[leaf_x*2], self.tree[leaf_x*2+1])
            

    def query(self, left, right):
        """
        :param left: queryの左idx(1-indexed)
        :param right: queryの右idx(1-indexed)
        大体queryは1-indexedなので、0-indexedにして
        left_0 = left - 1
        right_0 = right - 1
        半閉半開を考えるので、[left_0, right_0+1)
        つまり、[left_0, right)
        leftだけ-1する
        """
        left += self.num_end_leaves
        left -= 1
        right += self.num_end_leaves
        val_l = val_r = self.identity
        while right - left > 0:
            if left & 1:
                val_l = self.operator(val_l, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                val_r = self.operator(self.tree[right], val_r)
            left >>= 1
            right >>= 1
        return self.operator(val_l, val_r)


n, q = map(int, input().split())
a = list(map(int, input().split()))
st = segmentTree(a, max, 0)
res = list()

for _ in range(q):
    t, x, y = map(int, input().split())
    if t == 1:
        st.update(x - 1, y)
    elif t == 2:
        print(st.query(x, y))
    else:
        hi = n + 1
        lo = x - 1
        while hi - lo > 1:
            mid = (hi + lo) // 2
            if st.query(x, mid) >= y:
                hi = mid
            else:
                lo = mid
        print(lo + 1)

Solution (Python):
import sys
input = lambda: sys.stdin.readline()


def solve():
    def init(init_arr):
        global num, segfunc, ide_ele, seg
        segfunc = lambda x, y: max(x, y)
        ide_ele = 0
        num = 2 ** (n - 1).bit_length()
        seg = [ide_ele] * 2 * num
        for i in range(n):
            seg[i + num - 1] = init_arr[i]
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

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

    init(a)
    res = []

    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 1:
            update(a - 1, b)
        elif t == 2:
            res.append(query(a - 1, b))
        elif t == 3:
            ng = a - 1
            ok = n + 1
            while ok > ng + 1:
                mid = (ok + ng) // 2
                if query(ng, mid) >= b:
                    ok = mid
                else:
                    ng = mid
            res.append(ok)
    print("\n".join(map(str, res)))


solve()

Solution (Python):
import sys
input = lambda: sys.stdin.readline()


def solve():
    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

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

    segfunc = lambda x, y: max(x, y)
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(a)
    res = []

    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 1:
            update(a - 1, b)
        elif t == 2:
            res.append(query(a - 1, b))
        elif t == 3:
            ng = a - 1
            ok = n + 1
            while ok > ng + 1:
                mid = (ok + ng) // 2
                if query(ng, mid) >= b:
                    ok = mid
                else:
                    ng = mid
            res.append(ok)
    print("\n".join(map(str, res)))


solve()

Solution (Python):
def solve():
    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

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

    ide_ele = 0

    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(a)

    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 1:
            update(a - 1, b)
        elif t == 2:
            print(query(a - 1, b))
        elif t == 3:
            ng = a - 1
            ok = n + 1
            while ok > ng + 1:
                mid = (ok + ng) // 2
                if query(ng, mid) >= b:
                    ok = mid
                else:
                    ng = mid
            print(ok)


solve()

Solution (Python):



import sys
input = lambda: sys.stdin.readline().rstrip()

class SegmentTree:
    def __init__(self,n,p,unit,f):
        self.num=2**((n-1).bit_length())
        self.seg=[unit]*(self.num*2)
        for i in range(n):
            self.seg[self.num+i]=p[i]
        for i in range(self.num-1,0,-1):
            self.seg[i]=f(self.seg[i<<1],self.seg[(i<<1)+1])
        self.unit=unit
        self.f=f
    def update(self,i,x):
        i+=self.num
        self.seg[i]=x
        while i:
            i>>=1
            self.seg[i]=self.f(self.seg[i<<1],self.seg[(i<<1)+1])
    def query(self,l,r):
        ansl=ansr=self.unit
        l+=self.num
        r+=self.num-1
        if l==r:
            return self.seg[l]
        while l<r:
            if l&1:
                ansl=self.f(ansl,self.seg[l])
                l+=1
            if ~r&1:
                ansr=self.f(self.seg[r],ansr)
                r-=1
            l>>=1
            r>>=1
        if l==r:
            ansl=self.f(ansl,self.seg[l])
        return self.f(ansl,ansr)

n,q=map(int,input().split())
a=list(map(int,input().split()))
f=lambda x,y: max(x,y)
seg=SegmentTree(n,a,0,f)
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    seg.update(a-1,b)
  if t==2:
    print(seg.query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if seg.query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)