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.



Sample input:
5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3


Sample output:
3
3
2
6

Submission status: Accepted

Solution code:
from typing import Callable, Iterator, Optional, 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, values: Optional[Iterator[S]], n: int, e: S, op: Callable[[S, S], S]
    ) -> None:
        self._e = e
        self._op = op
        self._n = n
        self._size = 1 << (self._n - 1).bit_length()

        self._tree = [e] * 2 * self._size
        if values is None:
            return

        for i, values in enumerate(values, self._size):
            self._tree[i] = values
        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 staticrmq():
    # https://judge.yosupo.jp/problem/staticrmq
    import sys

    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    N, _ = map(int, readline().split())
    A = map(int, readline().split())
    LR = map(int, read().split())
    tree = SegmentTree(A, N, (10 ** 10) + 1, min)
    res = [tree.prod(l, r) for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, res)))


def practice2_j():
    # https://atcoder.jp/contests/practice2/tasks/practice2_j
    import sys

    readline = sys.stdin.readline

    N, Q = map(int, readline().split())
    A = map(int, readline().split())
    tree = SegmentTree(A, N, -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)))


def dsl_2_a():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
    N, Q, *X = map(int, open(0).read().split())
    tree = SegmentTree(None, N, 2 ** 31 - 1, min)
    res = []
    for com, x, y in zip(*[iter(X)] * 3):
        if com:
            res.append(tree.prod(x, y + 1))
        else:
            tree.set(x, y)
    print("\n".join(map(str, res)))


def abc125_c():
    # https://atcoder.jp/contests/abc125/tasks/abc125_c
    from math import gcd

    N, *A = map(int, open(0).read().split())
    tree = SegmentTree(A, N, 0, gcd)
    res = max(gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N))
    print(res)


if __name__ == "__main__":
    # staticrmq()
    practice2_j()
    # dsl_2_a()
    # abc125_c()

Submission status: Accepted

Solution code:
from typing import Callable, Iterator, 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: Iterator[S], n: int, e: S, op: Callable[[S, S], S]) -> None:
        self._e = e
        self._op = op
        self._n = n
        self._size = 1 << (self._n - 1).bit_length()

        self._tree = [e] * 2 * self._size
        for i, a in enumerate(a, self._size):
            self._tree[i] = a
        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 staticrmq():
    # https://judge.yosupo.jp/problem/staticrmq
    import sys

    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    N, _ = map(int, readline().split())
    A = map(int, readline().split())
    LR = map(int, read().split())
    tree = SegmentTree(A, N, (10 ** 10) + 1, min)
    res = [tree.prod(l, r) for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, res)))


def practice2_j():
    # https://atcoder.jp/contests/practice2/tasks/practice2_j
    import sys

    readline = sys.stdin.readline

    N, Q = map(int, readline().split())
    A = map(int, readline().split())
    tree = SegmentTree(A, N, -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)))


def dsl_2_a():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
    N, Q, *X = map(int, open(0).read().split())
    tree = SegmentTree([2 ** 31 - 1] * N, N, 2 ** 31 - 1, min)
    res = []
    for com, x, y in zip(*[iter(X)] * 3):
        if com:
            res.append(tree.prod(x, y + 1))
        else:
            tree.set(x, y)
    print("\n".join(map(str, res)))


def abc125_c():
    # https://atcoder.jp/contests/abc125/tasks/abc125_c
    from math import gcd

    N, *A = map(int, open(0).read().split())
    tree = SegmentTree(A, N, 0, gcd)
    res = max(gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N))
    print(res)


if __name__ == "__main__":
    # staticrmq()
    practice2_j()
    # dsl_2_a()
    # abc125_c()

Submission status: Accepted

Solution code:
class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def max_right(self, l, f):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        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.tree[l])):
                while l < self.size:
                    l = 2 * l
                    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, f):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        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.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
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

##################################################################################################################
import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
A = tuple(map(int, input().split()))
e = 0
op = lambda x, y : x if x > y else y
st = SegmentTree(N, op, e)
st.built(A)
res = []

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

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

Submission status: Accepted

Solution code:
class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def max_right(self, l, f):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        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.tree[l])):
                while l < self.size:
                    l = 2 * l
                    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, f):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        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.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
            sm = self.op(self.tree[r], sm)
            if (r & -r) == r: break
        return 0

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

##################################################################################################################
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
A = list(map(int, input().split()))
e = 0
op = lambda x, y : x if x > y else y
st = SegmentTree(N, op, e)
st.built(A)
res = []

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

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

Submission status: Accepted

Solution code:
#####################################################################################################
##### Lazy Propotional Segment tree (遅延区間比例セグメント木)
#####################################################################################################

"""
区間更新、区間取得が可能

セグ木の深さ毎でモノイド間の作用 g の振る舞いが異なってしまう場合がある。
実際のところ、作用 g は大域的作用である必要はなく、時間効率そのままで局所変数を一つ持たせて局所化することができる。
ただし、一般化された分配法則
g[i](x*y) = g[i<<1]x * g[(i<<1)|1]x
を満たす必要がある。

以下の例では、 セグ木の i 番目のノードを構成する要素の数（何個の要素の積か？）を l[i] として、
g[i]x = x*l[i]
という局所作用を考えている。

例)

RSQ and RUQ:
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4777823#2

# クエリ関数
ef = 0
f = lambda x, y : x+y
# 更新関数
eh = -(1<<24)
h = lambda x, y: x if x != eh else y
g = lambda x, y, l: x*l

#################################################################################
#################################################################################


解説
https://maspypy.com/segment-tree-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B72
https://smijake3.hatenablog.com/entry/2018/11/03/100133

解説（作用付きモノイド）
https://algo-logic.info/segment-tree/

参考コード（C++）
https://ei1333.github.io/library/library/structure/segment-tree/lazy-segment-tree.cpp.html

参考コード(python)
https://yukicoder.me/submissions/470340


"""


class LazyPropSegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        :param length: 添え字 i がいくつの要素を畳み込んだ値になっているか
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x, l: g(xh, x, l) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0
        self.length = [0]
        for i in range(l+1):
            self.length += [1<<(l-i)]*(1<<i)

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        size, tree, f = self.size, self.tree, self.f
        for i in range(self.n):
            tree[size + i] = array[i]
        for i in range(size - 1, 0, -1):
            tree[i] = f(tree[i<<1], tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        size, tree, lazy, eh = self.size, self.tree, self.lazy, self.eh
        i += size
        self.propagate_lazy(i)
        tree[i] = x
        lazy[i] = eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        size, tree, lazy, length, g = self.size, self.tree, self.lazy, self.length, self.g
        i += size
        self.propagate_lazy(i)
        return g(lazy[i], tree[i], length[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        size, lazy, h = self.size, self.lazy, self.h
        if l >= r:
            return
        l += size
        r += size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                lazy[r] = h(x, lazy[r])
            if l&1:
                lazy[l] = h(x, lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)の区間取得の結果を返す　(0-indexed)
        """
        size, tree, lazy, length, ef, f, g = self.size, self.tree, self.lazy, self.length, self.ef, self.f, self.g
        l += size
        r += size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = ef
        res_r = ef
        while l < r:
            if l & 1:
                res_l = f(res_l, g(lazy[l], tree[l], length[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = f(g(lazy[r], tree[r], length[r]), res_r)
            l >>= 1
            r >>= 1
        return f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        tree, lazy, length, eh, h, f, g = self.tree, self.lazy, self.length, self.eh, self.h, self.f, self.g
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if lazy[x] == eh:
                continue
            laz = lazy[x]
            lazy[(x<<1)|1] = h(laz, lazy[(x<<1)|1])
            lazy[x<<1] = h(laz, lazy[x<<1])
            tree[x] = g(laz, tree[x], length[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            lazy[x] = eh

    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        tree, lazy, length, f, g = self.tree, self.lazy, self.length, self.f, self.g
        while i>1:
            i>>=1
            tree[i] = f(g(lazy[i<<1], tree[i<<1], length[i<<1]), g(lazy[(i<<1)|1], tree[(i<<1)|1], length[i<<1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        size, tree, lazy, length, eh, h, g = self.size, self.tree, self.lazy, self.length, self.eh, self.h, self.g
        for x in range(1, size):
            if lazy[x] == eh:
                continue
            lazy[(x<<1)|1] = h(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = h(lazy[x], lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            lazy[x] = eh
        for xh, x in zip(lazy[size:size+self.n], tree[size:size+self.n]):
            yield g(xh,x,1)

    def __str__(self):
        return str(list(self))

    def debug(self):
        tree, lazy = self.tree, self.lazy
        def full_tree_pos(G):
            n = G.number_of_nodes()
            if n == 0: return {}
            pos = {0: (0.5, 0.9)}
            if n == 1: return pos
            i = 1
            while not n >= 2 ** i or not n < 2 ** (i + 1): i+=1
            height = i
            p_key, p_y, p_x = 0, 0.9, 0.5
            l_child = True
            for i in range(height):
                for j in range(2 ** (i + 1)):
                    if 2 ** (i + 1) + j - 1 < n:
                        if l_child == True:
                            pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1)
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            l_child = False
                        else:
                            pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1)
                            l_child = True
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            p_key += 1
                            (p_x, p_y) = pos[p_key]
            return pos

        import networkx as nx
        import matplotlib.pyplot as plt
        A = tree[1:]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("tree-{0}.png".format(self.plt_cnt))
        plt.clf()

        A = lazy[1:-1]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("lazy-{0}.png".format(self.plt_cnt))
        plt.clf()
        self.plt_cnt += 1

##################################################################################################################
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
A = list(map(int, input().split()))
ef = 0
eh = 0
f = lambda x, y: x if x > y else y
g = lambda x, y, s: x if x > y else y
h = lambda x, y: x if x > y else y
st = LazyPropSegmentTree(N, f, g, h, ef, eh)
st.built(A)
res = []

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

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