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:
class Segment_Tree():
    def __init__(self,N,calc,unit,L=[]):
        """calcを演算とするN項のSegment Treeを作成

        N:要素数
        calc:演算(2変数関数,モノイド)
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        """
        self.calc=calc
        self.unit=unit

        N=max(N,len(L))

        k=1
        d=1

        while k<N:
            k*=2
            d+=1


        X=[unit]*(k-1)+L+[unit]*(k-len(L))

        self.num=k
        self.depth=d

        for i in range(k-2,-1,-1):
            X[i]=calc(X[2*i+1],X[2*i+2])

        self.data=X

    def index(self,k,index=0):
        return self.data[(self.num-1)+(k-index)]

    def update(self,k,x,index=0):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """

        m=(self.num-1)+(k-index)
        self.data[m]=x

        for _ in range(self.depth):
            m=(m-1)//2
            self.data[m]=self.calc(self.data[2*m+1],self.data[2*m+2])


    def sub_array(self,From,To,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__sub_array_second(A,B+1,0,0,self.num)

    def __sub_array_second(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.unit
        elif a<=l and r<=b:
            return self.data[k]
        else:
            alpha=self.__sub_array_second(a,b,2*k+1,l,(l+r)//2)
            beta=self.__sub_array_second(a,b,2*k+2,(l+r)//2,r)
            return self.calc(alpha,beta)

    def all_prod(self):
        return self.data[0]

    def max_right(self,l,r,cond,index=0):
        """以下の2つをともに満たすxの1つを返す.\n
        (1) r=l or cond(data[l]*data[l+1]*...*d[r-1]):True
        (2) r=x or cond(data[l]*data[l+1]*...*data[r]):False
        ※fが単調減少の時,cond(data[l]*...*data[r-1])を満たす最大のrとなる.

        cond:関数(引数が同じならば結果も同じ)
        cond(unit):True
        0<=l<=r<=n
        """
        l-=index
        assert 0<=l<=r<=self.num,"添字が範囲外"
        assert cond(self.unit),"単位元が条件を満たさない."

        if l==self.num:
            return self.num

        l+=(self.num-1)
        sm=self.unit

        calc=self.calc
        while True:
            while l%2:
                l=(l-1)>>1

            if not cond(calc(sm,self.data[l])):
                while l<self.num-1:
                    l=2*l+1

                    if cond(calc(sm,self.data[l])):
                        sm=calc(sm,self.data[l])
                        l+=1

                return min(l-(self.num-1)+index,r)

            sm=calc(sm,self.data[l])
            l+=1

            if not (l&(-l)) != l:
                break

        return r+index
#================================================
N,Q=map(int,input().split())
A=list(map(int,input().split()))

S=Segment_Tree(N,lambda x,y:max(x,y),-float("inf"),A)

X=[]
for _ in range(Q):
    T,alpha,beta=map(int,input().split())

    if T==1:
        S.update(alpha,beta,1)
    elif T==2:
        X.append(S.sub_array(alpha,beta,1))
    else:
        X.append(S.max_right(alpha,N,lambda x:x<beta,1))

print("\n".join(map(str,X)))

Submission status: Wrong Answer

Solution code:
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
ctypedef long long LL
# cython: cdivision=True
from libc.stdio cimport scanf
from libcpp.vector cimport vector
ctypedef vector[LL] vec

cdef class SegmentTree():
    cdef LL num,n
    cdef vec tree

    def __init__(self,vec A):
        cdef LL n,i
        n = A.size()
        self.n = n
        self.num = 1 << (n-1).bit_length()
        self.tree = vec(2*self.num,0)
        for i in range(n):
            self.tree[self.num + i] = A[i]
        for i in range(self.num-1,0,-1):
            self.tree[i] = max(self.tree[2*i],self.tree[2*i+1])

    cdef void update(self,LL k,LL x):
        k += self.num
        self.tree[k] = x
        while k>1:
            self.tree[k>>1] = max(self.tree[k],self.tree[k^1])
            k >>= 1

    cdef LL query(self,LL l,LL r):
        cdef LL res
        res = 0
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                res = max(res,self.tree[l])
                l += 1
            if r&1:
                res = max(res,self.tree[r-1])
            l >>= 1
            r >>= 1
        return res

    cdef LL bisect_l(self,LL l,LL r,LL x):
        cdef LL Lmin,Rmin,pos
        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] >= x:
                    Rmin = r
            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 self.n


cdef LL N,Q,i
cdef vec A

scanf("%lld %lld",&N,&Q)
A = vec(N,-1)
for i in range(N):
    scanf("%lld",&A[i])

cdef SegmentTree S = SegmentTree(A)
cdef LL t,x,v

for i in range(Q):
    scanf("%lld %lld %lld",&t,&x,&v)
    if t==1:
        S.update(x-1,v)
    elif t==2:
        print(S.query(x-1,v))
    else:
        print(S.bisect_l(x-1,N,v)+1)
'''
import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q < p:
            return ide_ele
        p += num - 1
        q += num - 1
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # seg tree初期値 (単位元)
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    def isOK(mid, m, value):
        a = query(m, mid)
        return a >= value


    B = A[::]

    for _ in range(Q):
        T, X, V = [int(x) for x in input().split()]
        if T == 1:
            update(X - 1, V)
            B[X - 1] = V
        elif T == 2:
            print(query(X - 1, V - 1))
        else:
            a = query(X - 1, N - 1)
            if a < V:
                print(N + 1)
            else:
                if B[X - 1] >= V:
                    print(X)
                    continue
                ok = N - 1
                ng = X - 1

                while abs(ok - ng) > 1:
                    mid = (ok + ng) // 2
                    if isOK(mid, X - 1, V):
                        ok = mid
                    else:
                        ng = mid

                print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # seg tree初期値 (単位元)
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    def isOK(mid, m, value):
        a = query(m, mid)
        return a <= value


    B = A[::]

    for _ in range(Q):
        T, X, V = [int(x) for x in input().split()]
        if T == 1:
            update(X - 1, V)
            B[X - 1] = V
        elif T == 2:
            print(query(X - 1, V))
        else:
            a = query(X - 1, N)
            if a < V:
                print(N + 1)
            else:
                if B[X - 1] >= V:
                    print(X)
                    continue
                ok = N
                ng = X

                while abs(ok - ng) > 1:
                    mid = (ok + ng) // 2
                    if isOK(mid, X - 1, V):
                        ok = mid
                    else:
                        ng = mid

                print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        for i in range(n):
            seg[i + num - 1] = init_val[i]

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # seg tree初期値 (単位元)
    n = N
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(A)

    def isOK(mid, m, value):
        a = query(m, mid)
        return a <= value


    B = A[::]

    for _ in range(Q):
        T, X, V = [int(x) for x in input().split()]
        if T == 1:
            update(X - 1, V)
            B[X - 1] = V
        elif T == 2:
            print(query(X - 1, V - 1))
        else:
            a = query(X - 1, N - 1)
            if a < V:
                print(N + 1)
            else:
                if B[X - 1] >= V:
                    print(X)
                    continue
                ok = N - 1
                ng = X - 1

                while abs(ok - ng) > 1:
                    mid = (ok + ng) // 2
                    if isOK(mid, X - 1, V):
                        ok = mid
                    else:
                        ng = mid

                print(ok + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x-1
  node[y]=a
  while y:
    y=(y-1)>>1
    node[y]=node[-3](node[(y<<1)+1],node[(y+1)<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k
  while True:
    if node[-1]<=x+1:
      return x-node[-1]+1
    if cond(node[(x<<1)+1]):
      x=(x<<1)+1
    else:
      x=(x<<1)+2

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and (node[-1]>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if x&(1<<i):
      if cond(node[(node[-1]>>i)+(x>>i)]):
        return bis_min_k(node,(node[-1]>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,Q=map(int,input().split())
A=list(map(int,input().split()))
X=[]
init(N+1,X,-1,lambda x,y:max(x,y))
for i in range(N):
  upd(X,i,A[i])
t,a,b=0,0,0
for i in range(Q):
  t,a,b=map(int,input().split())
  if t==1:
    upd(X,a-1,b)
  elif t==2:
    print(query(X,a-1,b))
  else:
    a=bis_min(X,a-1,N,lambda x:b<=x)
    if a==X[-1]:
      print(N+1)
    else:
      print(a+1)

Submission status: Wrong Answer

Solution code:
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x-1
  node[y]=a
  while y:
    y=(y-1)>>1
    node[y]=node[-3](node[(y<<1)+1],node[(y+1)<<1])

def query(node,l_q,r_q,k,l_m,r_m): #ここの引数の(k,l_m,r_m)は(0,0,node[-1])を渡す
  if r_q<=l_m or r_m<=l_q:
    return node[-2]
  if l_q<=l_m and r_m<=r_q:
    return node[k]
  l_a=query(node,l_q,r_q,2*k+1,l_m,(l_m+r_m)//2)
  r_a=query(node,l_q,r_q,2*k+2,(l_m+r_m)//2,r_m)
  return node[-3](l_a,r_a)

N,Q=map(int,input().split())
A=list(map(int,input().split()))
X=[]
init(N+1,X,-1,lambda x,y:max(x,y))
for i in range(N):
  upd(X,i,A[i])
t,a,b=0,0,0
for i in range(Q):
  t,a,b=map(int,input().split())
  if t==1:
    upd(X,a-1,b)
  elif t==2:
    print(query(X,a-1,b,0,0,X[-1]))
  else:
    l,r,m=a,N,0
    while r>l:
      m=(l+r+1)>>1
      if query(X,a-1,m,0,0,X[-1])>=b:
        r=min(r,m-1)
      else:
        l=m
    print(l+1)

Submission status: Wrong Answer

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

class SegmentTree:

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

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * self.n
        else:
            l = len(length_or_list)
            self.n = 1 << ((l - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + [self.e] * (self.n - l)
            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):
        l += self.n
        left_folded = self.e
        l //= l & -l
        while l > 1:
            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
            l //= l & -l
        return self.n

    # 未verify
    def min_left(self, r, f):
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e

        r //= r & -r
        r -= 1
        while r > 0:
            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 = f(self.func(self.data[r], right_folded))
                        r -= 1
                return r + 1 - self.n 
            r //= r & -r
            r -= 1
        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: Wrong Answer

Solution code:
class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
def binary_search2(func, n_min, n_max):
    left,right=n_min,n_max
    y_left, y_right = func(left), func(right)
    while right-left>1:
        middle = (left+right)//2
        y_middle = func(middle)
        if y_left==y_middle: left=middle
        else: right=middle

    return left
  
def exists(x):
  return seg.fold(x,N) >= b
      
N,Q=map(int,input().split())
*A,=map(int,input().split())
seg = SegTree(N,max,0)
seg.build(A)
for i in range(Q):
  t,a,b = map(int,input().split())
  if t==1:
    seg.set_val(a-1,b)
  elif t == 2:
    print(seg.fold(a-1,b))
  else:
    if seg.fold(a-1,N)<b:
      print(N+1)
      continue
    print(binary_search2(exists,a-1,N)+1)

Submission status: Wrong Answer

Solution code:
from sys import stdin


class SegmentTree:
    _op = None
    _e = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for e in it:
            result = op(result, e)
        return result


readline = stdin.readline

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

st = SegmentTree(N - 1, max, -1)
st.build(A)

result = []
for _ in range(Q):
    q = readline()
    if q[0] in '13':
        T, X, V = map(int, q.split())
        if T == 1:
            st.update(X - 1, V)
        elif T == 3:
            ok = N + 1
            ng = X - 1
            while abs(ng - ok) > 1:
                m = (ok + ng) // 2
                if st.query(0, m) > V:
                    ok = m
                else:
                    ng = m
            result.append(ok)
    elif q[0] == '2':
        T, L, R = map(int, q.split())
        result.append(st.query(L - 1, R))
print(*result, sep='\n')

Submission status: Wrong Answer

Solution code:
from sys import stdin


class SegmentTree:
    _op = None
    _e = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for e in it:
            result = op(result, e)
        return result


readline = stdin.readline

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

st = SegmentTree(N - 1, max, -1)
st.build(A)

result = []
for _ in range(Q):
    q = readline()
    if q[0] in '13':
        T, X, V = map(int, q.split())
        if T == 1:
            st.update(X - 1, V)
        elif T == 3:
            ok = N + 1
            ng = X - 1
            while abs(ng - ok) > 1:
                m = (ok + ng) // 2
                if st.query(0, m) >= V:
                    ok = m
                else:
                    ng = m
            result.append(ok)
    elif q[0] == '2':
        T, L, R = map(int, q.split())
        result.append(st.query(L - 1, R))
print(*result, sep='\n')

Submission status: Wrong Answer

Solution code:
class Segment_Tree_Exception(Exception):
    pass

class Segment_Tree():
    def __init__(self,N,calc,unit,L=[]):
        """calcを演算とするN項のSegment Treeを作成

        N:要素数
        calc:演算(2変数関数,モノイド)
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        """
        self.calc=calc
        self.unit=unit

        N=max(N,len(L))

        k=1
        d=1

        while k<N:
            k*=2
            d+=1


        X=[unit]*(k-1)+L+[unit]*(k-len(L))

        self.num=k
        self.depth=d

        for i in range(k-2,-1,-1):
            X[i]=calc(X[2*i+1],X[2*i+2])

        self.data=X

    def index(self,k,index=0):
        return self.data[(self.num-1)+(k-index)]

    def update(self,k,x,index=0):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """

        m=(self.num-1)+(k-index)
        self.data[m]=x

        for _ in range(self.depth):
            m=(m-1)//2
            self.data[m]=self.calc(self.data[2*m+1],self.data[2*m+2])


    def sub_array(self,From,To,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__sub_array_second(A,B+1,0,0,self.num)

    def __sub_array_second(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.unit
        elif a<=l and r<=b:
            return self.data[k]
        else:
            alpha=self.__sub_array_second(a,b,2*k+1,l,(l+r)//2)
            beta=self.__sub_array_second(a,b,2*k+2,(l+r)//2,r)
            return self.calc(alpha,beta)

def General_Binary_Increase_Search(L,R,cond,Integer=True,ep=1/(1<<20)):
    """条件式が単調増加であるとき,一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """
    if not(cond(R)):
        return None

    if Integer:
        R+=1
        while R-L>1:
            C=L+(R-L)//2
            if cond(C):
                R=C
            else:
                L=C
        return R
    else:
        while (R-L)>=ep:
            C=L+(R-L)/2
            if cond(C):
                R=C
            else:
                L=C
        return R
#================================================
N,Q=map(int,input().split())
A=list(map(int,input().split()))

S=Segment_Tree(N,lambda x,y:max(x,y),-float("inf"),A)

X=[]
for _ in range(Q):
    T,alpha,beta=map(int,input().split())

    if T==1:
        S.update(alpha,beta,1)
    elif T==2:
        X.append(S.sub_array(alpha,beta,1))
    else:
        Y=General_Binary_Increase_Search(alpha,N,lambda x:S.sub_array(alpha,x,1)>=beta)
        if Y==None:
            X.append(N+1)
        else:
            X.append(Y)

print("\n".join(map(str,X)))