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):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r)]
        ans = -float("inf")
        while q:
            k,l,r = q.pop()
            if r<=a or b<=l:
                pass
            elif a<=l and r<=b:
                ans = max(ans, self.seg[k])
            else:
                q.append((2*k+1,l,(l+r)//2))
                q.append((2*k+2,(l+r)//2,r)) 
        return ans
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックス(0,1,...,self.num-1)の最小
        条件を満たすものが存在しないとき、self.numを返す
        """
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r,True)] 
        ans = self.num
        while q:
            k,l,r,b = q.pop()
            if b:
                if self.seg[k]<x or r<=a or b<=l: 
                    pass
                elif k>=self.num-1: 
                    ans = min(ans, k - (self.num-1))
                    return ans
                else:
                    
                    q.append((2*k+2,(l+r)//2,r,False))
                    
                    q.append((2*k+1,l,(l+r)//2,True))
            else:
                if ans<self.num:
                    return ans
                q.append((k+1,r,2*r-l,True))
        return ans
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return self.num
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+1,l,(l+r)//2)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+2,(l+r)//2,r)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n+1:
            print(n+1)
        else:
            print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r)]
        ans = -float("inf")
        while q:
            k,l,r = q.pop()
            if r<=a or b<=l:
                pass
            elif a<=l and r<=b:
                ans = max(ans, self.seg[k])
            else:
                q.append((2*k+1,l,(l+r)//2))
                q.append((2*k+2,(l+r)//2,r)) 
        return ans
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックス(0,1,...,self.num-1)の最小
        条件を満たすものが存在しないとき、self.numを返す
        """
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r,True)] 
        ans = self.num
        while q:
            k,l,r,b = q.pop()
            if b:
                if self.seg[k]<x or r<=a or b<=l: 
                    pass
                elif k>=self.num-1: 
                    ans = min(ans, k - (self.num-1))
                else:
                    
                    q.append((2*k+2,(l+r)//2,r,False))
                    
                    q.append((2*k+1,l,(l+r)//2,True))
            else:
                if ans<self.num:
                    return ans
                q.append((k+1,r,2*r-l,True))
        return ans
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return self.num
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+1,l,(l+r)//2)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+2,(l+r)//2,r)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n+1:
            print(n+1)
        else:
            print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])


    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r)]
        ans = -float("inf")
        while q:
            k,l,r = q.pop()
            if r<=a or b<=l:
                pass
            elif a<=l and r<=b:
                ans = max(ans, self.seg[k])
            else:
                q.append((2*k+1,l,(l+r)//2))
                q.append((2*k+2,(l+r)//2,r)) 
        return ans
    
    
    
    
    
    
    
    
    
    
    
    
    
    def find_right(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最大
        """
        return self._find_right(a,b,x,k=0,l=0,r=self.num)
    def _find_right(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return -1
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vr = self._find_right(a,b,x,2*k+2,(l+r)//2,r)
            if vr>=0:
                return vr
            else:
                return self._find_right(a,b,x,2*k+1,l,(l+r)//2)
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return self.num
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+1,l,(l+r)//2)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+2,(l+r)//2,r)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n+1:
            print(n+1)
        else:
            print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num <<= 1
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[(k<<1)+1], self.seg[(k<<1)+2])


    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)>>1
        while k >= 0:
            self.seg[k] = max(self.seg[(k<<1)+1], self.seg[(k<<1)+2])
            k = (k-1)>>1
    def query(self,a,b):
        return self._query(a,b,0,0,self.num)
    def _query(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値, [l,r): ノードkの表す区間
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return -float("inf")
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            return max(self._query(a,b,(k<<1)+1,l,(l+r)>>1),self._query(a,b,(k<<1)+2,(l+r)>>1,r))
    def find_right(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最大
        """
        return self._find_right(a,b,x,k=0,l=0,r=self.num)
    def _find_right(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return -1
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vr = self._find_right(a,b,x,(k<<1)+2,(l+r)>>1,r)
            if vr>=0:
                return vr
            else:
                return self._find_right(a,b,x,(k<<1)+1,l,(l+r)>>1)
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return self.num
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,(k<<1)+1,l,(l+r)>>1)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,(k<<1)+2,(l+r)>>1,r)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,(k<<1)+1,l,(l+r)>>1),self.query_index(a,b,(k<<1)+2,(l+r)>>1,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[(k<<1)+1]>=self.seg[(k<<1)+2]:
                return self._index((k<<1)+1)
            else:
                return self._index((k<<1)+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n+1:
            print(n+1)
        else:
            print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])


    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    def query(self,a,b):
        return self._query(a,b,0,0,self.num)
    def _query(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値, [l,r): ノードkの表す区間
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return -float("inf")
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            return max(self._query(a,b,2*k+1,l,(l+r)//2),self._query(a,b,2*k+2,(l+r)//2,r))
    def find_right(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最大
        """
        return self._find_right(a,b,x,k=0,l=0,r=self.num)
    def _find_right(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return -1
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vr = self._find_right(a,b,x,2*k+2,(l+r)//2,r)
            if vr>=0:
                return vr
            else:
                return self._find_right(a,b,x,2*k+1,l,(l+r)//2)
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: 
            return self.num
        elif k>=self.num-1: 
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+1,l,(l+r)//2)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+2,(l+r)//2,r)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n+1:
            print(n+1)
        else:
            print(res)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)


class SegmentTree:
    
    
    
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() 
        self.default = default
        self.data = [default]*(self.size*2) 
        self.f = f

    def initialize(self, A):
        for i, ai in enumerate(A):
            self.update(i, ai)
        return self

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[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.data[l])
                l += 1
            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) 
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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


def main():
    N, Q = LI()
    A = LI()
    query = LIR(Q)
    tree = SegmentTree(N, f=max, default=-1).initialize(A)

    for t, a, b in query:
        if t == 1:
            tree.update(a-1, b)
        elif t == 2:
            print(tree.query(a-1, b))
        else:
            print(min(tree.lower_bound(a-1, b), N) + 1)



if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)


class SegmentTree:
    
    
    
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() 
        self.default = default
        self.data = [default]*(self.size*2) 
        self.f = f

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[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.data[l])
                l += 1
            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) 
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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


def main():
    N, Q = LI()
    A = LI()
    query = LIR(Q)
    tree = SegmentTree(N, f=max, default=-1)
    for i, ai in enumerate(A):
        tree.update(i, ai)

    for t, a, b in query:
        if t == 1:
            tree.update(a-1, b)
        elif t == 2:
            print(tree.query(a-1, b))
        else:
            print(min(tree.lower_bound(a-1, b), N) + 1)



if __name__ == '__main__':
    main()

Solution (Python):
class segtree:
  
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  
  def get(s, p):
    return s.d[p + s.size]
 
  
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  
  def all_prod(s): return s.d[1]
 
  
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
 
import sys
    
def e():
  return 0
 
def op(s, t):
  return max(s, t)
 
N, Q = list(map(int, input().split()))
A = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]

seg = segtree(A, op, e)

for q in Query:
  if q[0] == 1:
    _, x, v = q
    seg.set(x - 1 , v)
  elif q[0] == 2:
    _, l, r = q
    print(seg.prod(l - 1, r))
  elif q[0] == 3:
    _, x, v = q
    def g(n):
      return n < v
    print(seg.max_right(x - 1, g) + 1)

Solution (Python):
class segtree:
  
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  
  def get(s, p):
    return s.d[p + s.size]
 
  
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  
  def all_prod(s): return s.d[1]
 
  
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
 
import sys
    
def e():
  return 0
 
def op(s, t):
  return max(s, t)
 
N, Q = list(map(int, input().split()))
A = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]

seg = segtree(A, op, e)

for q in Query:
  if q[0] == 1:
    _, x, v = q
    seg.set(x - 1 , v)
  elif q[0] == 2:
    _, l, r = q
    print(seg.prod(l - 1, r))
  elif q[0] == 3:
    _, x, v = q
    def g(n):
      return n < v
    print(seg.max_right(x - 1, g) + 1)