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:
class SegTree:
    
    __slots__ = ["n", "data", "f", "id"]
    
    def __init__(self, li, func, identity):
        self.n = len(li)
        self.data = li*2
        self.f = func
        self.id = identity
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.f(self.data[2*i], self.data[2*i+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 //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = self.id
        while l < r:
            if l % 2:
                res = self.f(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = self.f(res, self.data[r])
            l //= 2
            r //= 2
        return res
    
    def max_right(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        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[2*idx])):
                idx = 2*idx
            else:
                temp = self.f(temp, self.data[2*idx])
                idx = 2*idx+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 % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        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[2*idx+1], temp)):
                idx = 2*idx+1
            else:
                temp = self.f(temp, self.data[2*idx+1], temp)
                idx = 2*idx
        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, -1)
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)

Submission status: Accepted

Solution code:
from typing import Callable, TypeVar, List
import sys
input = sys.stdin.readline
T = TypeVar('T')


class SegTree:
    def __init__(self, v: List[T], op: Callable[[T, T], T], e: Callable[[], T]) -> None:
        self._n = len(v)
        self.log = (self._n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e() for _ in range(2 * self.size)]
        self.op = op
        self.e = e
        for i in range(self._n):
            self.d[self.size + i] = v[i]
        for i in reversed(range(1, self.size)):
            self.__update__(i)

    @classmethod
    def init_e(cls, n: int, op: Callable[[T, T], T], e: Callable[[], T]) -> 'SegTree':
        return cls([e for _ in range(n)], op, e)

    def set(self, p: int, x: T) -> None:
        assert 0 <= p < self._n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.__update__(p >> i)

    def get(self, p: int) -> T:
        assert 0 <= p < self._n
        return self.d[p + self.size]

    def prod(self, l: int, r: int) -> T:
        assert 0 <= l <= self._n and 0 <= r <= self._n
        sml = self.e()
        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) -> T:
        return self.d[1]

    def max_right(self, l: int, f: Callable[[T], bool]):
        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 l % 2 == 0:
                l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l *= 2
                    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:
                return self._n

    def min_left(self, r: int, f: Callable[[T], bool]):
        assert 0 <= r <= self._n
        assert f(self.e())
        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:
                return 0

    def __update__(self, k: int) -> None:
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])


n, q = map(int, input().split())
a = list(map(int, input().split()))
seg = SegTree(a, max, lambda: -1)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class SegmentTree:
    def __init__(self, n, func, e, arrange=None):
        self.init(n)
        self.func = func
        self.e = e
        self.make_arrange(arrange)
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2 - 1
        self.N -= 1
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e]*(self.size)
            return
        self.segment = [0]*(self.N) + arrange + [self.e]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.func(self.segment[2*i+1], self.segment[2*i+2])
    
    def update(self, i, x):
        i += (self.N-1)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.func(self.segment[2*i+1], self.segment[2*i+2])
    
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.e
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            res = self.func(find_l, find_r)
            return res

    def count(self, l, r):
        return self.find(l-1, r, 0, 0, self.size-self.N)
    
    def bisect_sub(self, a, b, k, l, r, x):
        if r <= a or b <= l:
            return b+1
        if self.segment[k] < x:
            return b+1
        if k >= self.N:
            return r
        
        find_l = self.bisect_sub(a, b, 2*k+1, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
        return find_r

        

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 0, 0, self.size-self.N, x)
    

def main():
    n, q = map(int, input().split())
    p = list(map(int, input().split()))
    seg = SegmentTree(n, max, 0, arrange=p)

    res = []
    for i in range(q):
        a, b, c = list(map(int, input().split()))
        if a == 1:
            seg.update(b, c)
        elif a == 2:
            ans = seg.count(b, c)
            res.append(ans)
        else:
            ans = seg.bisect(b, n, c)
            res.append(ans)

    print(*res, sep="\n")
            

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class SegmentTree:
    '''
    Segment tree。区間を表す関数の引数は全て閉区間で統一する(search系の戻り値を考慮)
    --------
    n:要素数, func:演算(モノイド), e:単位元(モノイド), init_list:初期値
    '''
    def __init__(self, n, func=lambda x, y : max(x, y), e = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [e] * self.node_n
        self.f = func
        self.e = e

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

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

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

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

    def query(self, l, r):
        '''
        閉区間[l, r]の演算結果
        '''
        assert 0 <= l <= r < self.leaf_n
        left_val = self.e
        right_val = self.e
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。check_func(e)はTrueである必要がある。
        --------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.e))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.e
        while True:
            while i & 1 != 0: # iを左端とする最上の層まで移動
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #下の左側に移動
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1
    
    def search_min_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の r を返す。存在しない場合-1を返す。
        --------
        例：最大値がv以上になる区間を探す
            f = max
            check_func = lambda(x):x >= v
        '''
        assert(0 <= l < self.leaf_n)
        i = l + self.offset
        left_val = self.e
        while True:
            x = self.f(left_val, self.tree[i])
            if check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #下の左側
                    x = self.f(left_val, self.tree[i])
                    if not check_func(x):
                        left_val = x
                        i += 1
                j = i - self.offset
                if self.n <= j:
                    return -1
                return j if check_func(self.f(left_val, self.tree[i])) else -1
            if i & 1 == 0:
                left_val = x
            if (i + 1) & (i + 2) == 0: #iが右端
                return -1
            i >>= 1


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

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


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

Submission status: Accepted

Solution code:
class SegmentTree:
    '''
    Segment tree。区間を表す関数の引数は全て閉区間で統一する(search系の戻り値を考慮)
    --------
    n:要素数, func:演算(モノイド), e:単位元(モノイド), init_list:初期値
    '''
    def __init__(self, n, func=lambda x, y : max(x, y), e = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [e] * self.node_n
        self.f = func
        self.e = e

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

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

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

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

    def query(self, l, r):
        '''
        閉区間[l, r]の演算結果
        '''
        assert 0 <= l <= r < self.leaf_n
        left_val = self.e
        right_val = self.e
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。check_func(e)はTrueである必要がある。
        --------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.e))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.e
        while True:
            while i & 1 != 0: # iを左端とする最上の層まで移動
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #下の左側に移動
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1
    
    def search_min_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の r を返す。存在しない場合-1を返す。
        --------
        例：最大値がv以上になる区間を探す
            f = max
            check_func = lambda(x):x >= v
        '''
        assert(0 <= l < self.leaf_n)
        i = l + self.offset
        left_val = self.e
        while True:
            x = self.f(left_val, self.tree[i])
            if check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #下の左側
                    x = self.f(left_val, self.tree[i])
                    if not check_func(x):
                        left_val = x
                        i += 1
                j = i - self.offset
                if self.n <= j:
                    return -1
                return j if check_func(self.f(left_val, self.tree[i])) else -1
            if i & 1 == 0:
                left_val = x
            if (i + 1) & (i + 2) == 0: #iが右端
                return -1
            i >>= 1


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

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

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

Submission status: Accepted

Solution code:
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def 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 //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res
    
    def max_right(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = 0
        for idx in (left_li + right_li[::-1]):
            if not check(max(temp, self.data[idx])):
                temp = max(temp, self.data[idx])
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(max(temp, self.data[2*idx])):
                idx = 2*idx
            else:
                temp = max(temp, self.data[2*idx])
                idx = 2*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 = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ans = seg.max_right(x, n, lambda x: x>=v)
        if ans == -1:
            print(n+1)
        else:
            print(ans+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # assert 0 <= l <= self.__len

        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        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.__len

    def __getitem__(self, key):
        return self.__tree[key + self.__size]



@mt
def slv(N, Q, A, T):
    st = SegmentTree(A, max, 0)
    ans = []
    for t, x, y in T:
        if t == 1:
            st.update(x-1, y)
        elif t == 2:
            ans.append(st.query(x-1, y))
        else:
            ans.append(st.max_right(x-1, lambda x: x < y)+1)

    return ans



def main():
    N, Q = read_int_n()
    A = read_int_n()
    T = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, A, T), sep='\n')


if __name__ == '__main__':
    main()