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:
# 2冪サイズじゃない二分探索の実装、思いつきません...
# 二分探索はsegtree.hppから拝借。

class SegmentTree:

    __slots__ = ["func", "e", "original_size", "n", "data"]

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * self.n
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def all_folded(self):
        return self.data[1]

    def __getitem__(self, index):
        return self.data[self.n + index]

    def max_right(self, l, f):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            l //= l & -l
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    # 未verify
    def min_left(self, r, f):
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n 
            if r == r & -r:
                break
        return 0


def yosupo():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = SegmentTree(list(map(int, input().split())), lambda a, b: a + b, 0)
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.folded(b, c))
        else:
            seg.replace(b, seg[b] + c)

def aoj():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    seg = SegmentTree([2 ** 31 - 1] * N, min, 2 ** 31 - 1)
    for _ in range(Q):
        q, x, y = map(int, input().split())
        if q == 0:
            seg.replace(x, y)
        else:
            print(seg.folded(x, y+1))

def main():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    As = list(map(int, input().split()))
    seg = SegmentTree(As, max, -1)
    for _ in range(Q):
        T, X, V = map(int, input().split())
        if T == 1:
            seg.replace(X - 1, V)
        elif T == 2:
            print(seg.folded(X-1, V))
        else:
            print(seg.max_right(X-1, lambda a: a < V)+ 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2冪サイズじゃない二分探索の実装、思いつきません...
# 二分探索はsegtree.hppから拝借。

class SegmentTree:

    __slots__ = ["func", "e", "original_size", "n", "data"]

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * self.n
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def all_folded(self):
        return self.data[1]

    def __getitem__(self, index):
        return self.data[self.n + index]

    def max_right(self, l, f):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            l //= l & -l
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    # 未verify
    def min_left(self, r, f):
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n 
            if r == r & -r:
                break
        return 0


def yosupo():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = map(int, input().split())
    seg = SegmentTree(list(map(int, input().split())), lambda a, b: a + b, 0)
    for _ in range(Q):
        a, b, c = map(int, input().split())
        if a:
            print(seg.folded(b, c))
        else:
            seg.replace(b, seg[b] + c)

def aoj():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    seg = SegmentTree([2 ** 31 - 1] * N, min, 2 ** 31 - 1)
    for _ in range(Q):
        q, x, y = map(int, input().split())
        if q == 0:
            seg.replace(x, y)
        else:
            print(seg.folded(x, y+1))

def main():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    As = list(map(int, input().split()))
    seg = SegmentTree(As, max, -1)
    for _ in range(Q):
        T, X, V = map(int, input().split())
        if T == 1:
            seg.replace(X - 1, V)
        elif T == 2:
            print(seg.folded(X-1, V))
        else:
            print(min(N, seg.max_right(X-1, lambda a: a < V)) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)

# Segment Tree


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    global WIDTH
    WIDTH = width
    set_depth((width - 1).bit_length() + 1)


def point_set(table, pos, value, binop):
    pos = pos + NONLEAF_SIZE
    table[pos] = value
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
        )


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def bisect_left(table, left, right, value):
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    left_left = None
    right_left = None
    while left < right:
        if left & 1:
            if left_left is None and table[left] >= value:
                left_left = left
            left += 1
        if right & 1:
            if table[right - 1] >= value:
                right_left = right - 1
        left >>= 1
        right >>= 1

    if left_left is not None:
        pos = left_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    elif right_left is not None:
        pos = right_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    else:
        return WIDTH


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


def main():
    N, Q = map(int, input().split())
    AS = list(map(int, input().split()))
    set_width(N)

    table = [0] * SEGTREE_SIZE
    table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = AS
    full_up(table, max)

    for _q in range(Q):
        q, x, y = map(int, input().split())
        if q == 1:
            # update
            point_set(table, x - 1, y, max)
        elif q == 2:
            # find
            print(range_reduce(table, x - 1, y, max, -INF))
        else:
            print(bisect_left(table, x - 1, N, y) + 1)


# tests
T1 = """
5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
3
2
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


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

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

# SegmentTree
class SegmentTree:

  def __init__(self, n, p, unit, f, g, h):
    num = 2**((n-1).bit_length())
    seg = [unit]*(num*2)
    self.lazy = [None]*(num*2)
    for i in range(n):
      seg[num+i] = p[i]
    for i in range(num-1, 0, -1):
      seg[i] = f(seg[i << 1], seg[(i << 1)+1])
    self.num = num
    self.seg = seg
    self.unit = unit
    self.flag = False
    self.f = f
    self.g = g
    self.h = h

  def gindex(self, l, r):
    l += self.num
    r += self.num
    lm = (l//(l & -l)) >> 1
    rm = (r//(r & -r)) >> 1
    mm = max(lm, rm)
    r -= 1
    while l < r:
      if r <= rm:
        yield r
      if l <= lm:
        yield l
      l >>= 1
      r >>= 1
    while l:
      if l <= mm:
        yield l
      l >>= 1

  def propagates(self, ids):
    num = self.num
    g = self.g
    h = self.h
    for i in reversed(ids):
      v = self.lazy[i]
      if v is None:
        continue
      # ここ！！！！！！！！！！！！！
      # ここ！！！！！！！！！！！！！

      newv = (v[0]//2,v[1]//2)

      # ここ！！！！！！！！！！！！！
      # ここ！！！！！！！！！！！！！
      if (i << 1) < num:
        self.lazy[i << 1] = h(self.lazy[i << 1], newv)
        self.lazy[(i << 1)+1] = h(self.lazy[(i << 1)+1], newv)
      self.seg[i << 1] = g(self.seg[i << 1], newv)
      self.seg[(i << 1)+1] = g(self.seg[(i << 1)+1], newv)
      self.lazy[i] = None

  def query(self, l, r):
    f = self.f
    if self.flag:
      *ids, = self.gindex(l, r)
      self.propagates(ids)
    ansl = ansr = self.unit
    l += self.num
    r += self.num-1
    if l == r:
      return self.seg[l]
    while l < r:
      if l & 1:
        ansl = f(ansl, self.seg[l])
        l += 1
      if r & 1 == 0:
        ansr = f(self.seg[r], ansr)
        r -= 1
      l >>= 1
      r >>= 1
    if l == r:
      ansl = f(ansl, self.seg[l])
    return f(ansl, ansr)

  def update1(self, i, x):
    i += self.num
    f = self.f
    self.seg[i] = x
    while i:
      i >>= 1
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])

  def update2(self, l, r, x):
    self.flag = True
    *ids, = self.gindex(l, r)
    self.propagates(ids)
    num = self.num
    f = self.f
    g = self.g
    h = self.h
    l += num
    r += num-1
    if l == r:
      self.seg[l] = g(self.seg[l], x)
      for i in ids:
        self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
      return
    while l < r:
      if l & 1:
        if l < num:
          self.lazy[l] = h(self.lazy[l], x)
        self.seg[l] = g(self.seg[l], x)
        l += 1
      if r & 1 == 0:
        if r < num:
          self.lazy[r] = h(self.lazy[r], x)
        self.seg[r] = g(self.seg[r], x)
        r -= 1
      l >>= 1
      r >>= 1
      x = f(x, x)
    if l == r:
      self.lazy[l] = h(self.lazy[l], x)
      self.seg[l] = g(self.seg[l], x)
    for i in ids:
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
  
  def update(self, i, x):
    if type(i) is int:
      self.update1(i, x)
    else:
      self.update2(i[0], i[1], x)

n,q=map(int,input().split())
a=list(map(int,input().split()))
f=lambda x,y: max(x,y)
seg=SegmentTree(n,a,0,f,0,0)
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    seg.update(a-1,b)
  if t==2:
    print(seg.query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if seg.query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.range = [(-1,n)] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
            self.range[self.num + i] = (i,i)
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
            self.range[i] = (self.range[2 * i][0],self.range[2 * i + 1][1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

    def bisect_l(self,l,r,x):
        l += self.num
        r += self.num
        Lmin = -1
        Rmin = -1
        while l<r:
            if l & 1:
                if self.tree[l] >= x and Lmin==-1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.tree[r-1] >=x:
                    Rmin = r-1
            l >>= 1
            r >>= 1

        if Lmin != -1:
            pos = Lmin
            while pos<self.num:
                if self.tree[2 * pos] >=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            return pos-self.num
        elif Rmin != -1:
            pos = Rmin
            while pos<self.num:
                if self.tree[2 * pos] >=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            return pos-self.num
        else:
            return N

import sys

input = sys.stdin.readline

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

Seg = SegmentTree(A,max,0)

for _ in range(Q):
    query = list(map(int,input().split()))
    if query[0] == 1:
        gomi,idx,val = query
        Seg.update(idx-1,val)
    elif query[0] == 2:
        gomi,l,r = query
        print(Seg.query(l-1,r))
    else:
        gomi,l,val = query
        print(Seg.bisect_l(l-1,N,val)+1)

Submission status: Accepted

Solution code:
# Date [ 2020-09-08 00:35:49 ]
# Problem [ j.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class SegmentTree:
    def __init__(self, array, function, identify):
        self.length = len(array)
        self.func, self.ide_ele = function, identify

        self.size = 1 << (self.length-1).bit_length()
        self.data = [self.ide_ele] * 2*self.size
        # set
        for i in range(self.length):
            self.data[self.size + i] = array[i]
        # build
        for i in range(self.size-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i + 1])

    def update(self, idx, x):
        idx += self.size
        self.data[idx] = x
        while idx > 0:
            idx >>= 1
            self.data[idx] = self.func(self.data[2*idx], self.data[2*idx + 1])
 
    def query(self, l, r):
        l += self.size; r += self.size+1
        l_ret = r_ret = self.ide_ele
        while l < r:
            if l & 1:
                l_ret = self.func(l_ret, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                r_ret = self.func(self.data[r], r_ret)
            l >>= 1; r >>= 1
        return self.func(l_ret, r_ret)

    def get(self, idx):
        return self.data[idx+self.size]

def Main():
    n, q = read_ints()
    a = read_int_list()
    seg = SegmentTree(a, max, -float('inf'))
    for _ in range(q):
        t, x, v = read_ints()
        if t == 1:
            seg.update(~-x, v)
        elif t == 2:
            print(seg.query(~-x, ~-v))
        else:
            l = x - 1; r = n + 1
            while r - l > 1:
                mid = (l + r) // 2
                if seg.query(~-x, ~-mid) >= v:
                    r = mid
                else:
                    l = mid
            print(r)

if __name__ == '__main__':
    Main()

Submission status: Runtime Error

Solution code:
def segfunc(x,y):return max(x,y)
ide_ele=0
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
def isok(mid,key):
  return st.query(x-1,mid-1)>=key
def b_search(x,key):
  ng=x-1
  ok=n+1
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid,key):ok=mid
    else:ng=mid
  return ok
n,q=map(int,input().split())
a=list(map(int,input().split()))
st=segtree(a)
ans=[]
for _ in range(q):
  c,x,y=map(int,input().split())
  if c==1:st.update(x-1,y)
  elif c==2:ans+=[st.query(x-1,y)]
  else:ans+=[b_search(x,y)]
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
def segfunc(x,y):return max(x,y)
ide_ele=0
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
def isok(mid,key):
  return st.query(x,mid)>=key
def b_search(x,key):
  ng=x-1
  ok=n
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid,key):ok=mid
    else:ng=mid
  return ok+1
n,q=map(int,input().split())
a=list(map(int,input().split()))
st=segtree(a)
ans=[]
for _ in range(q):
  c,x,y=map(int,input().split())
  if c==1:st.update(x-1,y)
  elif c==2:ans+=[st.query(x-1,y)]
  else:ans+=[b_search(x,y)]
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__bit_code = """
def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
"""

atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)


_atcoder_segtree_code = """
import typing

# import atcoder._bit


class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = atcoder._bit._ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> 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) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n

        left += self._size
        sm = self._e

        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int,
                 f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)

        if right == 0:
            return 0

        right += self._size
        sm = self._e

        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

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

atcoder.segtree = types.ModuleType('atcoder.segtree')
exec(_atcoder_segtree_code, atcoder.segtree.__dict__)
atcoder.segtree.__dict__['atcoder'] = atcoder
atcoder.segtree.__dict__['atcoder._bit'] = atcoder._bit
SegTree = atcoder.segtree.SegTree

# https://atcoder.jp/contests/practice2/tasks/practice2_j

import sys

# from atcoder.segtree import SegTree


def main(seed) -> None:
    n, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    segtree = SegTree(max, -1, a)

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


if __name__ == '__main__':
    for i in range(100000):
        main(i)