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:
# 無限にメモリリークするバージョンなので修正必須

code_segtree = r"""
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include "structmember.h"

// >>> AtCoder >>>

#ifndef ATCODER_SEGTREE_HPP
#define ATCODER_SEGTREE_HPP 1

#include <algorithm>
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP
#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

#endif  // ATCODER_SEGTREE_HPP

// <<< AtCoder <<<

using namespace std;
using namespace atcoder;
#define PARSE_ARGS(types, ...) if(!PyArg_ParseTuple(args, types, __VA_ARGS__)) return NULL

static PyObject* segtree_op_py;
static PyObject* segtree_op(PyObject* a, PyObject* b){
    return PyObject_CallFunctionObjArgs(segtree_op_py, a, b, NULL);
}
static PyObject* segtree_e_py;
static PyObject* segtree_e(){
    return segtree_e_py;
}
static PyObject* segtree_f_py;
static bool segtree_f(PyObject* x){
    PyObject* pyfunc_res = PyObject_CallFunctionObjArgs(segtree_f_py, x, NULL);
    int res = PyObject_IsTrue(pyfunc_res);
    if(res == -1) PyErr_Format(PyExc_ValueError, "error in SegTree f");
    return (bool)res;
}
struct SegTree{
    PyObject_HEAD
    segtree<PyObject*, segtree_op, segtree_e>* seg;
    PyObject* op;
    PyObject* e;
    int n;
};

extern PyTypeObject SegTreeType;

static void SegTree_dealloc(SegTree* self){
    delete self->seg;
    Py_DECREF(self->op);
    Py_DECREF(self->e);
    Py_TYPE(self)->tp_free((PyObject*)self);
}
static PyObject* SegTree_new(PyTypeObject* type, PyObject* args, PyObject* kwds){
    SegTree* self;
    self = (SegTree*)type->tp_alloc(type, 0);
    return (PyObject*)self;
}
static inline void set_op_e(SegTree* self){
    segtree_op_py = self->op;
    segtree_e_py = self->e;
}
static int SegTree_init(SegTree* self, PyObject* args){
    if(Py_SIZE(args) != 3){
        self->op = Py_None;  // 何か入れておかないとヤバいことになる
        Py_INCREF(Py_None);
        self->e = Py_None;
        Py_INCREF(Py_None);
        PyErr_Format(PyExc_TypeError, "SegTree constructor expected 3 arguments (op, e, n), got %d", Py_SIZE(args));
        return -1;
    }
    PyObject* arg;
    if(!PyArg_ParseTuple(args, "OOO", &self->op, &self->e, &arg)) return -1;
    Py_INCREF(self->op);
    Py_INCREF(self->e);
    set_op_e(self);
    if(PyLong_Check(arg)){
        int n = (int)PyLong_AsLong(arg);
        if(PyErr_Occurred()) return -1;
        if(n < 0 || n > (int)1e8) {
            PyErr_Format(PyExc_ValueError, "constraint error in SegTree constructor (got %d)", n);
            return -1;
        }
        self->seg = new segtree<PyObject*, segtree_op, segtree_e>(n);
        self->n = n;
    }else{
        PyObject *iterator = PyObject_GetIter(arg);
        if(iterator==NULL) return -1;
        PyObject *item;
        vector<PyObject*> vec;
        if(Py_TYPE(arg)->tp_as_sequence != NULL) vec.reserve((int)Py_SIZE(arg));
        while(item = PyIter_Next(iterator)) {
            vec.emplace_back(item);
        }
        Py_DECREF(iterator);
        if (PyErr_Occurred()) return -1;
        self->seg = new segtree<PyObject*, segtree_op, segtree_e>(vec);
        self->n = (int)vec.size();
    }
    return 0;
}
static PyObject* SegTree_set(SegTree* self, PyObject* args){
    long p;
    PyObject* x;
    PARSE_ARGS("lO", &p, &x);
    if(p < 0 || p >= self->n){
        PyErr_Format(PyExc_IndexError, "SegTree set index out of range (size=%d, index=%d)", self->n, p);
        return (PyObject*)NULL;
    }
    Py_INCREF(x);  // 参照カウント増えるけど減らない…後で修正する
    set_op_e(self);
    self->seg->set((int)p, x);
    Py_RETURN_NONE;
}
static PyObject* SegTree_get(SegTree* self, PyObject* args){
    long p;
    PARSE_ARGS("l", &p);
    if(p < 0 || p >= self->n){
        PyErr_Format(PyExc_IndexError, "SegTree get index out of range (size=%d, index=%d)", self->n, p);
        return (PyObject*)NULL;
    }
    PyObject* res = self->seg->get((int)p);
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_prod(SegTree* self, PyObject* args){
    long l, r;
    PARSE_ARGS("ll", &l, &r);
    set_op_e(self);
    PyObject* res = self->seg->prod((int)l, (int)r);
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_all_prod(SegTree* self, PyObject* args){
    PyObject* res = self->seg->all_prod();
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_max_right(SegTree* self, PyObject* args){
    long l;
    PARSE_ARGS("lO", &l, &segtree_f_py);
    if(l < 0 || l > self->n){
        PyErr_Format(PyExc_IndexError, "SegTree max_right index out of range (size=%d, l=%d)", self->n, l);
        return (PyObject*)NULL;
    }
    set_op_e(self);
    int res = self->seg->max_right<segtree_f>((int)l);
    return Py_BuildValue("l", res);
}
static PyObject* SegTree_min_left(SegTree* self, PyObject* args){
    long r;
    PARSE_ARGS("lO", &r, &segtree_f_py);
    if(r < 0 || r > self->n){
        PyErr_Format(PyExc_IndexError, "SegTree max_right index out of range (size=%d, r=%d)", self->n, r);
        return (PyObject*)NULL;
    }
    set_op_e(self);
    int res = self->seg->min_left<segtree_f>((int)r);
    return Py_BuildValue("l", res);
}
static PyObject* SegTree_to_list(SegTree* self){
    PyObject* list = PyList_New(self->n);
    for(int i=0; i<self->n; i++){
        PyObject* val = self->seg->get(i);
        Py_INCREF(val);
        PyList_SET_ITEM(list, i, val);
    }
    return list;
}
static PyObject* SegTree_repr(PyObject* self){
    PyObject* list = SegTree_to_list((SegTree*)self);
    PyObject* res = PyUnicode_FromFormat("SegTree(%R)", list);
    Py_ReprLeave(self);
    Py_DECREF(list);
    return res;
}

static PyMethodDef SegTree_methods[] = {
    {"set", (PyCFunction)SegTree_set, METH_VARARGS, "Set item"},
    {"get", (PyCFunction)SegTree_get, METH_VARARGS, "Get item"},
    {"prod", (PyCFunction)SegTree_prod, METH_VARARGS, "Get item"},
    {"all_prod", (PyCFunction)SegTree_all_prod, METH_VARARGS, "Get item"},
    {"max_right", (PyCFunction)SegTree_max_right, METH_VARARGS, "Binary search on segtree"},
    {"min_left", (PyCFunction)SegTree_min_left, METH_VARARGS, "Binary search on segtree"},
    {NULL}  /* Sentinel */
};
PyTypeObject SegTreeType = {
    PyObject_HEAD_INIT(NULL)
    "atcoder.SegTree",                  /*tp_name*/
    sizeof(SegTree),                    /*tp_basicsize*/
    0,                                  /*tp_itemsize*/
    (destructor)SegTree_dealloc,        /*tp_dealloc*/
    0,                                  /*tp_print*/
    0,                                  /*tp_getattr*/
    0,                                  /*tp_setattr*/
    0,                                  /*reserved*/
    SegTree_repr,                       /*tp_repr*/
    0,                                  /*tp_as_number*/
    0,                                  /*tp_as_sequence*/
    0,                                  /*tp_as_mapping*/
    0,                                  /*tp_hash*/
    0,                                  /*tp_call*/
    0,                                  /*tp_str*/
    0,                                  /*tp_getattro*/
    0,                                  /*tp_setattro*/
    0,                                  /*tp_as_buffer*/
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
    0,                                  /*tp_doc*/
    0,                                  /*tp_traverse*/
    0,                                  /*tp_clear*/
    0,                                  /*tp_richcompare*/
    0,                                  /*tp_weaklistoffset*/
    0,                                  /*tp_iter*/
    0,                                  /*tp_iternext*/
    SegTree_methods,                    /*tp_methods*/
    0,                                  /*tp_members*/
    0,                                  /*tp_getset*/
    0,                                  /*tp_base*/
    0,                                  /*tp_dict*/
    0,                                  /*tp_descr_get*/
    0,                                  /*tp_descr_set*/
    0,                                  /*tp_dictoffset*/
    (initproc)SegTree_init,             /*tp_init*/
    0,                                  /*tp_alloc*/
    SegTree_new,                        /*tp_new*/
    0,                                  /*tp_free*/
    0,                                  /*tp_is_gc*/
    0,                                  /*tp_bases*/
    0,                                  /*tp_mro*/
    0,                                  /*tp_cache*/
    0,                                  /*tp_subclasses*/
    0,                                  /*tp_weaklist*/
    0,                                  /*tp_del*/
    0,                                  /*tp_version_tag*/
    0,                                  /*tp_finalize*/
};

static PyModuleDef atcodermodule = {
    PyModuleDef_HEAD_INIT,
    "atcoder",
    NULL,
    -1,
};

PyMODINIT_FUNC PyInit_atcoder(void)
{
    PyObject* m;
    if(PyType_Ready(&SegTreeType) < 0) return NULL;

    m = PyModule_Create(&atcodermodule);
    if(m == NULL) return NULL;

    Py_INCREF(&SegTreeType);
    if (PyModule_AddObject(m, "SegTree", (PyObject*)&SegTreeType) < 0) {
        Py_DECREF(&SegTreeType);
        Py_DECREF(m);
        return NULL;
    }

    return m;
}
"""
code_setup = r"""
from distutils.core import setup, Extension
module = Extension(
    "atcoder",
    sources=["atcoder_library_wrapper.cpp"],
    extra_compile_args=["-O3", "-march=native", "-std=c++14"]
)
setup(
    name="atcoder-library",
    version="0.0.1",
    description="wrapper for atcoder library",
    ext_modules=[module]
)
"""

import os
import sys
if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    with open("atcoder_library_wrapper.cpp", "w") as f:
        f.write(code_segtree)
    with open("setup.py", "w") as f:
        f.write(code_setup)
    os.system(f"{sys.executable} setup.py build_ext --inplace")


from atcoder import SegTree

def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    A = map(int, input().split())

    op = lambda a, b: a if a > b else b
    e = -1
    seg = SegTree(op, e, A)

    Ans = []
    m = map(int, sys.stdin.buffer.read().split())
    for t, x, v in zip(m, m, m):
        x -= 1
        if t == 1:
            seg.set(x, v)
        elif t == 2:
            ans = seg.prod(x, v)
            Ans.append(ans)
        else:
            ans = seg.max_right(x, lambda a: a < v) + 1
            Ans.append(ans)
    if Ans:
        print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
class segment_tree:
    __slots__ = ["op_M", "e_M","N","N0","dat"]
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        self.N = N
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k >>= 1
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k >>= 1

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]
    
    """
    f(x_l*...*x_{r-1}) が True になる最大の r 
    つまり TTTTFFFF となるとき、F となる最小の添え字
    存在しない場合 n が返る
    f(e_M) = True でないと壊れる
    """
    def max_right(self,l,f):
        if l == self.N: return self.N;
        l += self.N0
        sm = self.e_M
        while True:
            while l&1==0:
                l >>= 1
            
            if not f(self.op_M(sm,self.dat[l])):
                while l < self.N0:
                    l *= 2
                    if f(self.op_M(sm,self.dat[l])):
                        sm = self.op_M(sm,self.dat[l])
                        l += 1
                return l - self.N0

            sm = self.op_M(sm,self.dat[l])
            l += 1
            if (l & -l) == l: break
        
        return self.N

    """
    f(x_l*...*x_{r-1}) が True になる最小の l
    つまり FFFFTTTT となるとき、T となる最小の添え字
    存在しない場合 r が返る
    f(e_M) = True でないと壊れる
    """
    def min_left(self,r,f):
        if r == 0: return 0
        r += self.N0
        sm = self.e_M
        
        while True:
            r -= 1
            while r > 1 and r&1:
                r >>= 1

            if not f(self.op_M(self.dat[r],sm)):
                while r < self.N0:
                    r = r*2 + 1
                    if f(self.op_M(self.dat[r],sm)):
                        sm = self.op_M(self.dat[r],sm)
                        r -= 1
                return r + 1 - self.N0

            sm = self.op_M(self.dat[r],sm)
            if (r & -r) == r: break

        return 0




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

n,q = map(int, readline().split())
*a, = map(int, readline().split())

seg = segment_tree(n,max,0)
seg.build(a)

for _ in range(q):
    idx,p,v = map(int, readline().split())
    if idx==1:
        seg.update(p-1,v)
    elif idx==2:
        print(seg.query(p-1,v-1))
    else:
        print(seg.max_right(p-1,lambda x: x < v)+1)

Submission status: Accepted

Solution code:
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


def practice2_j():
    # https://atcoder.jp/contests/practice2/tasks/practice2_j
    N, _, *AQ = map(int, open(0).read().split())
    A, Q = AQ[:N], AQ[N:]
    tree = SegmentTree(A, -1, max)
    res = []
    for t, x, y in zip(*[iter(Q)] * 3):
        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 staticrmq():
    # https://judge.yosupo.jp/problem/staticrmq
    N, Q, *ALR = map(int, open(0).read().split())
    A, LR = ALR[:N], ALR[N:]
    tree = SegmentTree(A, (10 ** 10) + 1, min)
    res = [tree.prod(l, r) for l, r in zip(*[iter(LR)] * 2)]
    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, 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, 0, gcd)
    res = max(gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N))
    print(res)


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

Submission status: Accepted

Solution code:
from typing import Callable, List, Union

T = Union[int, str]


class SegmentTree:
    """Segment Tree"""

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

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

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

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

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

    def set(self, k: int, x: T) -> None:
        assert 0 <= k < self._n

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

    def prod(self, l: int, r: int) -> T:
        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 self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        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:
        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


def practice2_j():
    N, _, *AQ = map(int, open(0).read().split())
    A, Q = AQ[:N], AQ[N:]
    tree = SegmentTree(A, -1, max)
    res = []
    for t, x, y in zip(*[iter(Q)] * 3):
        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()

Submission status: Accepted

Solution code:
from typing import Callable, List, Union

T = Union[int, str]


class SegmentTree:
    """Segment Tree"""

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

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

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

    def get(self, k: int) -> T:
        # assert 0 <= k < self._n
        return self.tree[k + self._size]

    def set(self, k: int, x: T) -> None:
        # assert 0 <= k < self._n

        k += self._size
        self.tree[k] = x
        while k:
            k >>= 1
            self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def prod(self, l: int, r: int) -> T:
        # 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 self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        # 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:
        # 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


def practice2_j():
    N, _, *AQ = map(int, open(0).read().split())
    A, Q = AQ[:N], AQ[N:]
    tree = SegmentTree(A, max, -1)
    res = []
    for t, x, y in zip(*[iter(Q)] * 3):
        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()