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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### セグメント木

class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
#             for i,item in enumerate(a):
#                 self.update(i,item)
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    def query(self,a,b):
        return self._query(a,b,0,0,self.num)
    def _query(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値, [l,r): ノードkの表す区間
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return -float("inf")
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            return max(self._query(a,b,2*k+1,l,(l+r)//2),self._query(a,b,2*k+2,(l+r)//2,r))
    def find_right(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最大
        """
        return self._find_right(a,b,x,k=0,l=0,r=self.num)
    def _find_right(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: # x以上を満たせない or 区間が重複しない
            return -1
        elif k>=self.num-1: # 自身が葉
            return k - (self.num-1)
        else:
            vr = self._find_right(a,b,x,2*k+1,l,(l+r)//2)
            if vr>=0:
                return vr
            else:
                return self._find_right(a,b,x,2*k+2,(l+r)//2,r)
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: # x以上を満たせない or 区間が重複しない
            return self.num
        elif k>=self.num-1: # 自身が葉
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+2,(l+r)//2,r)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+1,l,(l+r)//2)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n+1:
            print(n+1)
        else:
            print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### セグメント木

class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
#             for i,item in enumerate(a):
#                 self.update(i,item)
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i+(self.num-1)
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    def query(self,a,b):
        return self._query(a,b,0,0,self.num)
    def _query(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値, [l,r): ノードkの表す区間
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return -float("inf")
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            return max(self._query(a,b,2*k+1,l,(l+r)//2),self._query(a,b,2*k+2,(l+r)//2,r))
    def find_right(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最大
        """
        return self._find_right(a,b,x,k=0,l=0,r=self.num)
    def _find_right(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: # x以上を満たせない or 区間が重複しない
            return -1
        elif k>=self.num-1: # 自身が葉
            return k - (self.num-1)
        else:
            vr = self._find_right(a,b,x,2*k+1,l,(l+r)//2)
            if vr>=0:
                return vr
            else:
                return self._find_right(a,b,x,2*k+2,(l+r)//2,r)
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: # x以上を満たせない or 区間が重複しない
            return self.num
        elif k>=self.num-1: # 自身が葉
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+2,(l+r)//2,r)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+1,l,(l+r)//2)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x-1,y))
    else:
        res = sg.find_left(x-1,n,y)+1
        if res>=n:
            print(n+1)
        else:
            print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### セグメント木

class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
#             for i,item in enumerate(a):
#                 self.update(i,item)
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i + self.num - 1
        self.seg[k] = x
        k = (k-1)//2
        while k >= 0:
            self.seg[k] = max(self.seg[2*k+1], self.seg[2*k+2])
            k = (k-1)//2
    def query(self,a,b):
        return self._query(a,b,0,0,self.num)
    def _query(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値, [l,r): ノードkの表す区間
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return -float("inf")
        elif a <= l and r <= b:
            return self.seg[k]
        else:
            return max(self._query(a,b,2*k+1,l,(l+r)//2),self._query(a,b,2*k+2,(l+r)//2,r))
    def find_right(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最大
        """
        return self._find_right(a,b,x,k=0,l=0,r=self.num)
    def _find_right(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: # x以上を満たせない or 区間が重複しない
            return -1
        elif k>=self.num-1: # 自身が葉
            return k - (self.num-1)
        else:
            vr = self._find_right(a,b,x,2*k+1,l,(l+r)//2)
            if vr>=0:
                return vr
            else:
                return self._find_right(a,b,x,2*k+2,(l+r)//2,r)
    def find_left(self,a,b,x):
        """[a,b)で値がx以上のインデックスの最小
        """
        return self._find_left(a,b,x,k=0,l=0,r=self.num)
    def _find_left(self,a,b,x,k,l,r):
        if self.seg[k]<x or r<=a or b<=l: # x以上を満たせない or 区間が重複しない
            return self.num
        elif k>=self.num-1: # 自身が葉
            return k - (self.num-1)
        else:
            vl = self._find_left(a,b,x,2*k+2,(l+r)//2,r)
            if vl<self.num:
                return vl
            else:
                return self._find_left(a,b,x,2*k+1,l,(l+r)//2)
    def query_index(self,a,b,k=0,l=0,r=None):
        """query(a,b,0,0,num):[a,b)の最大値
        最大値を与えるインデックスも返す
        """
        if r is None:
            r = self.num
        if r <= a or b <= l:
            return (-float("inf"), None)
        elif a <= l and r <= b:
            return (self.seg[k], self._index(k))
        else:
            return max(self.query_index(a,b,2*k+1,l,(l+r)//2),self.query_index(a,b,2*k+2,(l+r)//2,r))
    def _index(self, k):
        if k>=self.num:
            return k - (self.num-1)
        else:
            if self.seg[2*k+1]>=self.seg[2*k+2]:
                return self._index(2*k+1)
            else:
                return self._index(2*k+2)
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
    t,x,y = map(int, input().split())
    if t==1:
        sg.update(x-1,y)
    elif t==2:
        print(sg.query(x,y+1))
    else:
        res = sg.find_left(x,n,y)+1
        if res>=n:
            print(n+1)
        else:
            print(res)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

# reffer to: https://qiita.com/dn6049949/items/afa12d5d079f518de368
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.data = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[i*2+1])

    # [l, r)
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

    # You can use lower_bound only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    def lower_bound(self, x, v):
        x += self.size
        while self.data[x] < v:
            if x & 1: # x % 2 == 1
                if len(bin(x)) == len(bin(x+1)):
                    x += 1
                else:
                    return self.size
            else:
                x >>= 1
        while x < self.size:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.size


def main():
    N, Q = LI()
    A = LI()
    query = LIR(Q)
    tree = SegmentTree(N, f=max, default=-1)
    for i, ai in enumerate(A):
        tree.update(i, ai)

    for t, a, b in query:
        if t == 1:
            tree.update(a-1, b)
        elif t == 2:
            print(tree.query(a-1, b-1))
        else:
            print(min(tree.lower_bound(a-1, b), N)+1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class segtree:
  #セグメント木
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    return s.d[p + s.size]
 
  # 区間演算
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
 
import sys
    
def e():
  return 0
 
def op(s, t):
  return max(s, t)
 
N, Q = list(map(int, input().split()))
A = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]

seg = segtree(A, op, e)

for q in Query:
  if q[0] == 1:
    _, x, v = q
    seg.set(x - 1 , v)
  elif q[0] == 2:
    _, l, r = q
    print(seg.prod(l - 1, r))
  elif q[0] == 3:
    _, x, v = q
    def g(n):
      return n < v
    print(seg.max_right(x, g) + 1)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        #leaf->rootに向かって、apply func していく
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 #k=segTree上での k-th leafのidx
        self.data[k] = a

        while k > 0: #while not reach to root
            k = (k-1)//2 #goto its parent
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) #update

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: #R%2==1 
                R -= 1
                ret = self.func(ret, self.data[R-1]) #親が丸々区間に含まれない->はみ出したところを更新
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 #to parent
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        x:0-origin
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す(二分探索)

        存在しないなら、float("inf")をreturn している。
        """
        #区間の左端
        x+=self.n-1

        #data[x]が、v以上なるまで登る
        while self.data[x]<v:
            if x%2==0: #xが右のnodeなら、候補外になる
                if len(bin(x+1))==len(bin(x+2)):#一つ右に移動できるなら
                    x+=1
                else:#右に行けない->とりま大きい値をreturnしとく。(多分、全ての値が条件を満たさない時に、無限whileするのを防ぐ
                    return float("inf")

            else:#登る
                x>>=1

        # v<=data[x]を満たすように、できるだけ左(idxが小さい)に降る
        while x<self.n:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)+1)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        #leaf->rootに向かって、apply func していく
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 #k=segTree上での k-th leafのidx
        self.data[k] = a

        while k > 0: #while not reach to root
            k = (k-1)//2 #goto its parent
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) #update

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: #R%2==1 
                R -= 1
                ret = self.func(ret, self.data[R-1]) #親が丸々区間に含まれない->はみ出したところを更新
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 #to parent
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す
        """
        #区間の左端
        x+=self.n-1

        #data[x]が、v以上なるまで登る
        while self.data[x]<v:
            if x&0: #xが右のnodeなら
                if len(bin(x+2))==len(bin(x+3)):#一つ右に移動できるなら
                    x+=1
                else:#右に行けない->とりま大きい値をreturnしとく。(多分、全ての値が条件を満たさない時に、無限whileするのを防ぐ
                    return self.n

            else:
                x>>=1

        while x<self.n-1:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)+1)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        #leaf->rootに向かって、apply func していく
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 #k=segTree上での k-th leafのidx
        self.data[k] = a

        while k > 0: #while not reach to root
            k = (k-1)//2 #goto its parent
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) #update

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: #R%2==1 
                R -= 1
                ret = self.func(ret, self.data[R-1]) #親が丸々区間に含まれない->はみ出したところを更新
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 #to parent
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す
        """
        x+=self.n-1
        while self.data[x]<v:
            if x&1:
                if len(bin(x+2))==len(bin(x+3)):#右端でない?
                    x+=1
                else:
                    return self.n-1

            else:
                x>>=1

        while x<self.n-1:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)+1)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        #leaf->rootに向かって、apply func していく
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 #k=segTree上での k-th leafのidx
        self.data[k] = a

        while k > 0: #while not reach to root
            k = (k-1)//2 #goto its parent
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) #update

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: #R%2==1 
                R -= 1
                ret = self.func(ret, self.data[R-1]) #親が丸々区間に含まれない->はみ出したところを更新
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 #to parent
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す
        """
        x+=self.n-1
        while self.data[x]<v:
            if x%2==1:
                if len(bin(x+2))==len(bin(x+3)):#右端でない?
                    x+=1
                else:
                    return self.n-1

            else:
                x>>=1

        while x<self.n:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)+1)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

    def lower_bound_index(self,x,v):
        x+=self.n
        while self.data[x]<v:
            if x%2==1:
                if len(bin(x))==len(bin(x+1)):
                    x+=1
                else:
                    return self.n

            else:
                x>>=1
        while x<self.n:
            if self.data[2*x]>=v:
                x=2*x
            else:
                x=2*x+1
        return x-self.n



N,Q = map(int,input().split())
Seg = SegmentTree(N,lambda x,y:max(x,y),init=-1)
A = list(map(int,input().split()))
for i,a in enumerate(A):
    Seg.set(i,a)



Seg.build()

for _ in range(Q):
    t,a,b = map(int,input().split())
    if t==1:
        Seg.update(a-1,b)
    elif t==2:
        print(Seg.query(a-1,b))
    elif t==3:
        print(min(Seg.lower_bound_index(a-1,b),N)*1)