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):
mod = 1000000007
eps = 10**-9
 
 
def main():
    import sys
    input = sys.stdin.buffer.readline
    
    
    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
 
        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
 
        
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)
 
        
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1
 
    def check(val):
        return val >= v

    n,q = map(int,input().split())
    morty = list(map(int,input().split()))
    stree = SegmentTree(morty,segfunc=max,ident=-2000000000)

    for _ in range(q):
        t,x,v = map(int,input().split())
        if t == 1:
            stree.update(x, v)
        elif t==2:
            print(stree.query(x,v+1))
        else:
            print(stree.binsearch(x,n+1, check))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class SegTree():
	def __init__(self, a, func, idem):
		
		self.n = 1 << len(a).bit_length()
		self.size = len(a)
		self.func = func
		self.idem = idem
		self.node = [idem] * (2*self.n-1)
		for i in range(len(a)+self.n-2, -1, -1):
			if i >= self.n-1:
				self.node[i] = a[i-self.n+1]
			else:
				self.node[i] = self.func(self.node[2*i+1], self.node[2*i+2])

	def get(self, x):
		return self.node[x+self.n-1]

	def set(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = self.func(self.node[2*x+1], self.node[2*x+2])
		return

	
	def prod(self, l, r):
		L, R = l+self.n, r+self.n
		s_l, s_r = self.idem, self.idem
		while L<R:
			if R & 1:
				R -= 1
				s_r = self.func(self.node[R-1], s_r)
			if L & 1:
				s_l = self.func(s_l, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return self.func(s_l, s_r)

	
	def max_right(self, l, val):
		if l == self.size:
			return self.size
		L = l + self.n
		s = self.idem
		while True:
			while (L % 2 == 0):
				L >>= 1
			if not val(self.func(s, self.node[L-1])):
				while L < self.n:
					L <<= 1
					if val(self.func(s, self.node[L-1])):
						s = self.func(s, self.node[L-1])
						L += 1
				return L - self.n
			s = self.func(s, self.node[L-1])
			L += 1
			if (L & -L) == L:
				return self.size

	
	def min_left(self, r, val):
		if r == 0:
			return 0
		R = r + self.n
		s = self.idem
		while True:
			R -= 1
			while R > 1 and R % 2:
				R >>= 1
			if not val(self.func(self.node[R-1], s)):
				while R < self.n:
					R = (R << 1) + 1
					if val(self.func(self.node[R-1], s)):
						s = self.func(self.node[R-1], s)
						R -= 1
				return R + 1 - self.n
			s = self.func(self.node[R-1], s)
			if (R & -R) == R:
				return 0


n, q = map(int, input().split())
a = list(map(int, input().split()))
st = SegTree(a, max, 0)
for _ in range(q):
	t, x, y = map(int, input().split())
	if t == 1:
		st.set(x-1, y)
	elif t == 2:
		print(st.prod(x-1, y))
	else:
		print(st.max_right(x-1, lambda z: z < y) + 1)

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class SegTree():
	def __init__(self, a, func, idem):
		
		self.n = 1 << len(a).bit_length()
		self.size = len(a)
		self.func = func
		self.idem = idem
		self.node = [idem] * (2*self.n-1)
		for i in range(len(a)+self.n-2, -1, -1):
			if i >= self.n-1:
				self.node[i] = a[i-self.n+1]
			else:
				self.node[i] = self.func(self.node[2*i+1], self.node[2*i+2])

	def get(self, x):
		return self.node[x+self.n-1]

	def set(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = self.func(self.node[2*x+1], self.node[2*x+2])
		return

	
	def prod(self, l, r):
		L, R = l+self.n, r+self.n
		s_l, s_r = self.idem, self.idem
		while L<R:
			if R & 1:
				R -= 1
				s_r = self.func(self.node[R-1], s_r)
			if L & 1:
				s_l = self.func(s_l, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return self.func(s_l, s_r)

	
	def max_right(self, l, val):
		if l == self.size:
			return self.size
		L = l + self.n
		s = self.idem
		while True:
			while (L % 2 == 0):
				L >>= 1
			if not val(self.func(s, self.node[L-1])):
				while L < self.n:
					L <<= 1
					if val(self.func(s, self.node[L-1])):
						s = self.func(s, self.node[L-1])
						L += 1
				return L - self.n
			s = self.func(s, self.node[L-1])
			L += 1
			if (L & -L) == L:
				return self.size

	
	def min_left(self, r, val):
		if r == 0:
			return 0
		R = r + self.n
		s = self.idem
		while True:
			R -= 1
			while R > 1 and R % 2:
				R >>= 1
			if not val(self.func(self.node[R-1], s)):
				while R < self.n:
					R = (R << 1) + 1
					if val(self.func(self.node[R-1], s)):
						s = self.func(self.node[R-1], s)
						R -= 1
				return R + 1 - self.n
			s = self.func(self.node[R-1], s)
			if (R & -R) == R:
				return 0


n, q = map(int, input().split())
a = list(map(int, input().split()))
st = SegTree(a, max, 0)
for _ in range(q):
	t, x, y = map(int, input().split())
	if t == 1:
		st.set(x-1, y)
	elif t == 2:
		print(st.prod(x-1, y))
	else:
		print(st.max_right(x-1, lambda z: z < y) + 1)

Solution (Python):
from typing import Callable, List, TypeVar

S = TypeVar("S")


class SegmentTree:
    """Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
    """

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[S], e: S, op: Callable[[S, S], S]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0


def practice2_j():
    
    import sys

    readline = sys.stdin.readline

    N, Q = map(int, readline().split())
    (*A,) = map(int, readline().split())
    tree = SegmentTree(A, -1, max)
    res = []
    for _ in range(Q):
        t, x, y = map(int, readline().split())
        if t == 1:
            tree.set(x - 1, y)
        elif t == 2:
            res.append(tree.prod(x - 1, y))
        else:
            res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    practice2_j()

Solution (Python):
from typing import Callable, List, TypeVar

S = TypeVar("S")


class SegmentTree:
    """Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
    """

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[S], e: S, op: Callable[[S, S], S]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0



import sys

readline = sys.stdin.buffer.readline

N, Q = map(int, readline().split())
(*A,) = map(int, readline().split())
tree = SegmentTree(A, -1, max)
res = []
for _ in range(Q):
    t, x, y = map(int, readline().split())
    if t == 1:
        tree.set(x - 1, y)
    elif t == 2:
        res.append(tree.prod(x - 1, y))
    else:
        res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
print("\n".join(map(str, res)))

Solution (Python):
from typing import Callable, List, TypeVar

S = TypeVar("S")


class SegmentTree:
    """Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
    """

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[S], e: S, op: Callable[[S, S], S]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0


def practice2_j():
    
    import sys

    readline = sys.stdin.buffer.readline

    N, Q = map(int, readline().split())
    (*A,) = map(int, readline().split())
    tree = SegmentTree(A, -1, max)
    res = []
    for _ in range(Q):
        t, x, y = map(int, readline().split())
        if t == 1:
            tree.set(x - 1, y)
        elif t == 2:
            res.append(tree.prod(x - 1, y))
        else:
            res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    practice2_j()

Solution (Python):
class SegmentTree():
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def build(self, arr):
        
        for i in range(self.n):
            self.d[self.size + i] = arr[i]
        for i in range(1, self.size)[::-1]:
            self.update(i)

    def set(self, p, x):
        
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        
        return self.d[p + self.size]

    def prod(self, l, r):
        
        sml = smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def max_right(self, l, f):
        
        
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: break
        return self.n

    def min_left(self, r, f):
        
        
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: break
        return 0

import sys
input = sys.stdin.buffer.readline

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

st = SegmentTree(N, max, 0)
st.build(A)
res = []

for _ in range(Q):
    t, x, y = map(int, input().split())
    if t == 1:
        st.set(x - 1, y)
    elif t == 2:
        res.append(st.prod(x - 1, y))
    else:
        res.append(st.max_right(x - 1, lambda z: z < y) + 1)

print('\n'.join(map(str, res)))

Solution (Python):
from typing import Callable, List, TypeVar

T = TypeVar("T")

class SegmentTree:
    """Segment Tree"""

    __slots__ = ["e", "op", "_n", "_size", "tree"]

    def __init__(self, a: List[T], e: T, op: Callable[[T, T], T]) -> None:
        self.e = e
        self.op = op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: T) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> T:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> T:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> T:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[T], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0

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

tree = SegmentTree(a, -1, max)

for _ in range(q):
    t,x,y = map(int,input().split())
    if t == 1:
        tree.set(x-1, y)
    elif t == 2:
        print(tree.prod(x-1, y))
    else:
        print(tree.max_right(x-1, lambda n: n < y) + 1)