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():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 
        self.data[k] = a

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

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: 
                R -= 1
                ret = self.func(ret, self.data[R-1]) 
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        x:0-origin
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す(二分探索)

        存在しないなら、float("inf")をreturn している。
        """
        
        x+=self.n-1

        
        while self.data[x]<v:
            if x%2==0: 
                if len(bin(x+1))==len(bin(x+2)):
                    x+=1
                else:
                    return float("inf")

            else:
                x>>=1

        
        while x<self.n-1:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1 



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)+1)

Solution (Python):
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 
        self.data[k] = a

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

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: 
                R -= 1
                ret = self.func(ret, self.data[R-1]) 
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す
        """
        
        x+=self.n-1

        
        while self.data[x]<v:
            
            if x%2==0: 
                
                if len(bin(x+1))==len(bin(x+2)):
                    
                    x+=1
                else:
                    return float("inf")

            else:
                x>>=1
            

        while x<self.n-1:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)+1)

Solution (Python):
code = r"""




from libcpp cimport bool

from libcpp.vector cimport vector

cdef extern from "<atcoder/segtree>" namespace "atcoder" nogil:

    cdef cppclass segtree[S, OP, E]:

        segtree(vector[S] v)

        void set(int p, S x)

        S get(int p)

        S prod(int l, int r)

        S all_prod()

        int max_right[F](int l)

        int min_left[F](int r)

ctypedef long seg_t

cdef extern from *:

    ctypedef int op_t "myop"

    ctypedef int e_t "mye"

    ctypedef int f_t "myf"

    cdef seg_t myop(seg_t a, seg_t b) nogil

    cdef seg_t mye() nogil

    cdef bool myf(seg_t k) nogil

cdef seg_t myop(seg_t a, seg_t b) nogil:

    if a > b:

        return a

    else:

        return b

cdef seg_t mye() nogil:

    return -1000000000

cdef seg_t v

cdef bool myf(seg_t k) nogil:

    return k < v



from cython.parallel cimport prange

from libc.stdio cimport scanf, printf

cdef void main():

    cdef int n, q, i, t, u

    scanf('%d%d', &n, &q)

    cdef vector[seg_t] a = vector[seg_t](n)

    for i in prange(n, nogil=1): scanf('%ld', &a[i])

    cdef segtree[seg_t, op_t, e_t] *seg = new segtree[seg_t, op_t, e_t](a)

    for i in prange(q, nogil=1):

        scanf('%d%d%d', &t, &u, &v)

        if t == 1:

            seg.set(u - 1, v)

        elif t == 2:

            printf('%ld\n', seg.prod(u - 1, v))

        else:

            printf('%ld\n', seg.max_right[f_t](u - 1) + 1)

main()

"""
import zlib, base64
open("B.cpython-38-x86_64-linux-gnu.so", "wb").write(zlib.decompress(base64.b85decode("c%1CL33wCb_CG$8$
import B

Solution (Python):
code = r"""


from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/segtree>" namespace "atcoder" nogil:
    cdef cppclass segtree[S, OP, E]:
        segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        int max_right[F](int l)
        int min_left[F](int r)
ctypedef long seg_t
cdef extern from *:
    ctypedef int op_t "myop"
    ctypedef int e_t "mye"
    ctypedef int f_t "myf"
    cdef seg_t myop(seg_t a, seg_t b) nogil
    cdef seg_t mye() nogil
    cdef bool myf(seg_t k) nogil
cdef seg_t myop(seg_t a, seg_t b) nogil:
    if a > b:
        return a
    else:
        return b
cdef seg_t mye() nogil:
    return -1000000000
cdef seg_t v
cdef bool myf(seg_t k) nogil:
    return k < v

from cython.parallel cimport prange
from libc.stdio cimport scanf, printf
cdef void main():
    cdef int n, q, i, t, u
    scanf('%d%d', &n, &q)
    cdef vector[seg_t] a = vector[seg_t](n)
    for i in prange(n, nogil=1): scanf('%ld', &a[i])
    cdef segtree[seg_t, op_t, e_t] *seg = new segtree[seg_t, op_t, e_t](a)
    for i in prange(q, nogil=1):
        scanf('%d%d%d', &t, &u, &v)
        if t == 1:
            seg.set(u - 1, v)
        elif t == 2:
            printf('%ld\n', seg.prod(u - 1, v))
        else:
            printf('%ld\n', seg.max_right[f_t](u - 1) + 1)
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
code = r"""





from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/segtree>" namespace "atcoder":
    cdef cppclass segtree[S, OP, E]:
        segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        int max_right[F](int l)
        int min_left[F](int r)
ctypedef long seg_t
cdef extern from *:
    ctypedef int op "myop"
    ctypedef int e "mye"
    ctypedef int f "myf"
    cdef seg_t myop(seg_t a, seg_t b) nogil
    cdef seg_t mye() nogil
    cdef bool myf(seg_t k) nogil
cdef seg_t myop(seg_t a, seg_t b) nogil:
    if a > b:
        return a
    else:
        return b
cdef seg_t mye() nogil:
    return -1000000000
cdef seg_t v
cdef bool myf(seg_t k) nogil:
    return k < v
from libc.stdio cimport scanf, printf
cdef main():
    cdef int n, q, i, t, u
    scanf('%d%d', &n, &q)
    cdef vector[seg_t] a = vector[seg_t](n)
    for i in range(n): scanf('%ld', &a[i])
    cdef segtree[seg_t, op, e] *seg = new segtree[seg_t, op, e](a)
    for i in range(q):
        scanf('%d%d%d', &t, &u, &v)
        if t == 1:
            seg.set(u - 1, v)
        elif t == 2:
            printf('%ld\n', seg.prod(u - 1, v))
        else:
            printf('%ld\n', seg.max_right[f](u - 1) + 1)
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):



























class SegmentTree:
    
    
    
    def __init__(self, size, f=lambda x,y : min(x, y), idele=float('inf')):
        self.size = 2**(size-1).bit_length()    
        self.idele = idele                      
        self.f = f                              
        self.dat = [self.idele]*(self.size*2)   


    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 add(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.idele, self.idele 
        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


    def lower_bound_index(self, i, v):
        i += self.size
        while self.dat[i] < v:
            if i & 1:
                if len(bin(i)) == len(bin(i+1)):
                    i += 1
                else:
                    return self.size
            else:
                i >>= 1
        while i < self.size:
            if self.dat[2*i] >= v:
                i = 2*i
            else:
                i = 2*i + 1
        return i - self.size


    def init(self, a):
        for i, x in enumerate(a):
            
            self.dat[i + self.size] = x
        for i in range(self.size-1, -1, -1):
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

n, q = map(int, input().split())
a = list(map(int, input().split()))
sgt = SegmentTree(n, lambda x,y : max(x, y), -float('inf'))
sgt.init(a)
for _ in range(q):
    t, u, v = map(int, input().split())
    if t == 1:
        sgt.update(u-1, v)
    elif t == 2:
        print(sgt.query(u-1, v))
    else:
        print(min(sgt.lower_bound_index(u-1, v), n) + 1)

Solution (Python):



























class SegmentTree:
    
    
    
    def __init__(self, size, f=lambda x,y : min(x, y), idele=float('inf')):
        self.size = 2**(size-1).bit_length()    
        self.idele = idele                      
        self.f = f                              
        self.dat = [self.idele]*(self.size*2)   


    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 add(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.idele, self.idele 
        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


    def lower_bound_index(self, i, v):
        i += self.size
        while self.dat[i] < v:
            if i & 1:
                if len(bin(i)) == len(bin(i+1)):
                    i += 1
                else:
                    return self.size
            else:
                i >>= 1
        while i < self.size:
            if self.dat[2*i] >= v:
                i = 2*i
            else:
                i = 2*i + 1
        return i - self.size


    def init(self, a):
        for i, x in enumerate(a):
            
            self.dat[i + self.size] = x
        for i in range(self.size-1, -1, -1):
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

n, q = map(int, input().split())
a = list(map(int, input().split()))
sgt = SegmentTree(n, lambda x,y : max(x, y), -float('inf'))
sgt.init(a)
for _ in range(q):
    t, u, v = map(int, input().split())
    if t == 1:
        sgt.update(u-1, v)
    elif t == 2:
        print(sgt.query(u-1, v))
    else:
        print(min(sgt.lower_bound_index(u-1, v), n) + 1)

Solution (Python):
class SegTree:
    
    __slots__ = ["n", "data", "f", "id"]
    
    def __init__(self, li, func, identity):
        self.n = len(li)
        self.f = func
        self.id = identity
        self.data = [self.id]*self.n + li
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.f(self.data[i<<1], self.data[i<<1|1])
    
    def get(self, i):
        return self.data[i+self.n]
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i >>= 1
            self.data[i] = self.f(self.data[i<<1], self.data[i<<1|1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i >>= 1
            self.data[i] = self.f(self.data[i<<1], self.data[i<<1|1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = self.id
        while l < r:
            if l & 1:
                res = self.f(self.data[l], res)
                l += 1
            if r & 1:
                r -= 1
                res = self.f(res, self.data[r])
            l >>= 1
            r >>= 1
        return res
    
    def max_right(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l & 1:
                left_li.append(l)
                l += 1
            if r & 1:
                r -= 1
                right_li.append(r)
            l >>= 1
            r >>= 1
        temp = self.id
        for idx in (left_li + right_li[::-1]):
            if not check(self.f(temp, self.data[idx])):
                temp = self.f(temp, self.data[idx])
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(temp, self.data[idx<<1])):
                idx = idx<<1
            else:
                temp = self.f(temp, self.data[idx<<1])
                idx = idx<<1|1
        return idx - self.n
    
    def min_left(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l & 1:
                left_li.append(l)
                l += 1
            if r & 1:
                r -= 1
                right_li.append(r)
            l >>= 1
            r >>= 1
        temp = self.id
        for idx in (right_li + left_li[::-1]):
            if not check(self.f(self.data[idx], temp)):
                temp = self.f(self.data[idx], temp)
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(self.data[idx<<1|1], temp)):
                idx = idx<<1|1
            else:
                temp = self.f(temp, self.data[idx<<1|1], temp)
                idx = idx<<1
        return idx - self.n

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = SegTree(A, max, -float("inf"))
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:
        ans = seg.max_right(x, n, lambda x: x>=v)
        if ans == -1:
            print(n+1)
        else:
            print(ans+1)