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: Wrong Answer

Solution code:
from copy import copy
class Seg_Tree:
  def __init__(self,init_list,init_value,func=min):
    il_len=len(init_list)
    r=1
    while il_len>r:
      r*=2
    self.tree=[0 for i in range(r-1)]+copy(init_list)+[init_value for i in range(r-il_len)]
    self.func=func
    self.len=r
    self.init_value=init_value
    for i in range(r-2,-1,-1):
      self.tree[i]=self.func(self.tree[i*2+1],self.tree[i*2+2])
  
  def update(self,x,value):
    x+=self.len-1
    self.tree[x]=value
    x=(x-1)//2
    while x>=0:
      self.tree[x]=self.func(self.tree[x*2+1],self.tree[x*2+2])
      x=(x-1)//2
  
  def query(self,l,r,x=0):
    xl=x
    xr=x
    while xl<r-1:
      xl,xr=xl*2+1,xr*2+2
    if xr<l or r<xl:
      return self.init_value
    elif l<=xl and xr<=r:
      return self.tree[x]
    else:
      return self.func(self.query(l,r,x*2+1),self.query(l,r,x*2+2))


n,q=map(int,input().split())
a=list(map(int,input().split()))
st=Seg_Tree(a,-1,max)

for i in range(q):
  qu=list(map(int,input().split()))
  if qu[0]==1:
    st.update(qu[1]-1,qu[2])
  elif qu[0]==2:
    print(st.query(qu[1]-1,qu[2]-1))
  else:
    l,r=qu[1]-2,n
    while r-l!=1:
      t=(l+r)//2
      v=st.query(qu[1]-1,t)
      if v>=qu[2]:
        r=t
      else:
        l=t
    print(r+1)

Submission status: Wrong Answer

Solution code:
class segtree:
    ## define what you want to do ,(min, max)
    sta = -1
    func = max

    def __init__(self,n):
        self.size = n
        self.tree = [self.sta]*(2*n)

    def build(self, list):
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    ## take the value of [l,r) 
    def get(self,l,r):
        l += self.size
        r += self.size
        res = self.sta

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

    def max_right(self, l, x):
        if l == self.size:
            return l
        l += self.size
        res = self.sta
        check = True
        while check or (l & -l) != l:
            check = False
            while l%2 == 0:
                l >>= 1
            if not self.func(res,self.tree[l]) < x:
                while l < self.size:
                    l <<= 1
                    if self.func(res,self.tree[l]) < x:
                        res = self.func(res,self.tree[l])
                        l += 1
                return l - self.size
            res = self.func(res,self.tree[l])
            l += 1
        return self.size

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

seg = segtree(n)
seg.build(a)
for _ in range(q):
    t,x,v = map(int,input().split())
    if t == 1:
        seg.set(x-1,v)
    elif t == 2:
        print(seg.get(x-1,v))
    else:
        print(seg.max_right(x-1,v)+1)

Submission status: Wrong Answer

Solution code:
class segtree:
    ## define what you want to do ,(min, max)
    sta = -1
    func = max

    def __init__(self,n):
        self.size = n
        self.tree = [self.sta]*(2*n)

    def build(self, list):
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    ## take the value of [l,r) 
    def get(self,l,r):
        l += self.size
        r += self.size
        res = self.sta

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

    def max_right(self, l, x):
        if l == self.size:
            return l
        l += self.size
        res = self.sta
        check = True
        while check or (l & -l) != l:
            check = False
            while l%2 == 0:
                l >>= 1
            if x < self.func(res,self.tree[l]):
                while l < self.size:
                    l <<= 1
                    if not x < self.func(res,self.tree[l]):
                        res = self.func(res,self.tree[l])
                        l += 1
                return l - self.size
            res = self.func(res,self.tree[l])
            l += 1
        return self.size

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

seg = segtree(n)
seg.build(a)
for _ in range(q):
    t,x,v = map(int,input().split())
    if t == 1:
        seg.set(x-1,v)
    elif t == 2:
        print(seg.get(x-1,v))
    else:
        print(seg.max_right(x-1,v)+1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return max(x, y)


@njit((i8[:], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.empty(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:], i8, i8), cache=True)
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit((i8[:], i8, i8), cache=True)
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8[:], i8, i8), cache=True)
def max_right(seg, l, x):
    """[l,r) が ok であるような最大の r を返す"""
    N = len(seg) // 2

    def is_ok(v, x):
        return v < x

    v = None
    i = l + N
    while True:
        if not (i & 1):
            i >>= 1
            continue
        v1 = seg_f(v, seg[i])
        if is_ok(v1, x):
            if i == 1:
                return N
            v, i = v1, (i + 1) >> 1
        else:
            break
    while True:
        if i > N + N:
            break
        v1 = seg_f(v, seg[i])
        if is_ok(v1, x):
            v, i = v1, (i + 1) << 1
        else:
            i <<= 1
    i >>= 1
    return i - N

@njit((i8, i8[:], i8[:]), cache=True)
def main(N, A, query):
    seg = build(A)
    for i in range(0, len(query), 3):
        t, a, b = query[i:i + 3]
        if t == 1:
            set_val(seg, a - 1, b)
        elif t == 2:
            print(fold(seg, a - 1, b))
        elif t == 3:
            print(max_right(seg, a - 1, b) + 1)

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
query = np.array(read().split(), np.int64)

main(N, A, query)

Submission status: Wrong Answer

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() -> None:
    n, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))[::-1]

    segtree = SegTree(max, -1, a)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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, f: typing.Callable[[typing.Any], bool], 
                  left: int) -> 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() -> None:
    n, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    segtree = SegTree(max, 0, 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:
            pass
            # print(segtree.max_right(lambda v: v < y, x - 1) + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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 count(self, l, r):
        res = self.e
        l += self.N
        r += self.N
        while r - l:
            if not l & 1:
                res = self.func(res, self.segment[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.func(res, self.segment[r])
            l >>= 1
            r >>= 1
        return res
    
    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける
    """

    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: Wrong Answer

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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 count(self, l, r):
        res = self.e
        l += self.N-1
        r += self.N-1
        while r - l:
            if l & 1:
                res = self.func(res, self.segment[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.func(res, self.segment[r])
            l >>= 1
            r >>= 1
        return res
    
    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける
    """

    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: Wrong Answer

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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 count(self, l, r):
        res = self.e
        l += self.N - 1
        r += self.N - 1
        while r - l:
            if not l & 1:
                res = self.func(res, self.segment[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.func(res, self.segment[r])
            l >>= 1
            r >>= 1
        return res
    
    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける
    """

    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: Wrong Answer

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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 count(self, l, r):
        res = self.e
        l += self.N - 1
        r += self.N - 1
        while r - l:
            if not l & 1:
                res = self.func(res, self.segment[l])
                l += 1
            if r & 1:
                res = self.func(res, self.segment[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res
    
    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける
    """

    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()