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:
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        SEGTREE_TABLES.append(np.zeros(n2 << 1, dtype=np.int64))
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.size >> 1
        table[offset:offset + len(arr)] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[i] = max(table[ch], table[ch + 1])

    def segtree_update(ins, i, x):
        table = SEGTREE_TABLES[ins]
        offset = table.size >> 1
        i += offset
        table[i] = x
        while i > 1:
            ch = i
            i >>= 1
            table[i] = max(table[ch], table[ch ^ 1])

    def segtree_query(ins, l, r):
        """ max [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.size >> 1
        l += offset
        r += offset
        res = -1
        while l < r:
            if r & 1:
                res = max(res, table[r - 1])
            if l & 1:
                res = max(res, table[l])
                l += 1
            l >>= 1
            r >>= 1
        return res

    def segtree_search(ins, lo, x):
        """
        Get min i where lo <= i, A[i] >= x.
        Assume that a sentinel larger than x is inserted at the right end.
        """
        table = SEGTREE_TABLES[ins]
        offset = table.size >> 1
        i = lo + offset
        while table[i] < x:
            while i & 1:
                i >>= 1
            i += 1
        while i < offset:
            i <<= 1
            if table[i] < x:
                i += 1
        return i - offset

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.size >> 1
        i = 1
        while i <= offset:
            print(table[i:2 * i])
            i <<= 1

    n = inp[0]
    q = inp[1]
    aaa = inp[2:n + 2]
    ttt = inp[n + 2::3]
    xxx = inp[n + 3::3]
    yyy = inp[n + 4::3]
    INF = 1 << 60

    aaa = np.append(aaa, INF)
    ins = segtree_init(n + 1)
    segtree_build(ins, aaa)

    ans = []

    for i in range(q):
        if ttt[i] == 1:
            segtree_update(ins, xxx[i] - 1, yyy[i])
        elif ttt[i] == 2:
            res = segtree_query(ins, xxx[i] - 1, yyy[i])
            ans.append(res)
        else:
            res = segtree_search(ins, xxx[i] - 1, yyy[i])
            ans.append(res + 1)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        SEGTREE_TABLES.append([0] * (n2 << 1))
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = len(table) >> 1
        table[offset:offset + len(arr)] = list(arr)
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[i] = max(table[ch], table[ch + 1])

    def segtree_update(ins, i, x):
        table = SEGTREE_TABLES[ins]
        offset = len(table) >> 1
        i += offset
        table[i] = x
        while i > 1:
            ch = i
            i >>= 1
            table[i] = max(table[ch], table[ch ^ 1])

    def segtree_query(ins, l, r):
        """ max [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = len(table) >> 1
        l += offset
        r += offset
        res = -1
        while l < r:
            if r & 1:
                res = max(res, table[r - 1])
            if l & 1:
                res = max(res, table[l])
                l += 1
            l >>= 1
            r >>= 1
        return res

    def segtree_search(ins, lo, x):
        """
        Get min i where lo <= i, A[i] >= x.
        Assume that a sentinel larger than x is inserted at the right end.
        """
        table = SEGTREE_TABLES[ins]
        offset = len(table) >> 1
        i = lo + offset
        while table[i] < x:
            while i & 1:
                i >>= 1
            i += 1
        while i < offset:
            i <<= 1
            if table[i] < x:
                i += 1
        return i - offset

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = len(table) >> 1
        i = 1
        while i <= offset:
            print(table[i:2 * i])
            i <<= 1

    n = inp[0]
    q = inp[1]
    aaa = inp[2:n + 2]
    ttt = inp[n + 2::3]
    xxx = inp[n + 3::3]
    yyy = inp[n + 4::3]
    INF = 1 << 60

    aaa = np.append(aaa, INF)
    ins = segtree_init(n + 1)
    segtree_build(ins, aaa)

    ans = []

    for i in range(q):
        if ttt[i] == 1:
            segtree_update(ins, xxx[i] - 1, yyy[i])
        elif ttt[i] == 2:
            res = segtree_query(ins, xxx[i] - 1, yyy[i])
            ans.append(res)
        else:
            res = segtree_search(ins, xxx[i] - 1, yyy[i])
            ans.append(res + 1)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.buffer.readline

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

st = SegmentTree(A, max, 0)
res = list()

for _ in range(Q):
    t, x, y = map(int, input().split())
    if t == 1:
        st.set(x - 1, y)
    elif t == 2:
        res.append(st.query(x - 1, y))
    else:
        hi = N + 1
        lo = x - 1
        while hi - lo > 1:
            mid = (hi + lo) // 2
            if st.query(x - 1, mid) >= y:
                hi = mid
            else:
                lo = mid
        res.append(lo + 1)

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
from copy import *
import sys
S=sys.stdin.readlines()

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
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<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])
      x+=1
    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+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

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]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,Q=map(int,S[0].split())
A=list(map(int,S[1].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,S[i+2].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>N:
      print(N+1)
    else:
      print(a+1)

Submission status: Accepted

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
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<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])
      x+=1
    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+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

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]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-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>N:
      print(N+1)
    else:
      print(a+1)

Submission status: Accepted

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-10**18):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

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

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

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

    st = SegmentTree(n=n, f=max, default=-1)
    for i, ai in enumerate(a):
        st.update(i, ai)

    for _ in range(q):
        t, x, v = map(int, input().split())
        if t == 1:
            st.update(x-1, v)
        elif t == 2:
            print(st.query(x-1, v))
        else:
            print(min(st.min_index(x-1, v), n) + 1)

main()

Submission status: Accepted

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7
# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    def __init__(self, n, f=max, default=-10**18):
        self.num_leaf = 1
        while self.num_leaf < n:
            self.num_leaf *= 2
        self.data = [default] * (2*self.num_leaf)
        self.f = f

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

    # return f(a[l:r])
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1: # l % 2 == 1
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1: # r % 2 == 0
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1 # l //= 2
            r >>= 1 # r //= 2
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

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

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

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

    st = SegmentTree(n=n, f=max, default=-1)
    for i, ai in enumerate(a):
        st.update(i, ai)

    ans = []
    for _ in range(q):
        t, x, v = map(int, input().split())
        if t == 1:
            st.update(x-1, v)
        elif t == 2:
            ans.append(st.query(x-1, v))
        else:
            ans.append(min(st.lower_bound_index(x-1, v), n) + 1)
    
    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7
# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    def __init__(self, n, f=max, default=-10**18):
        self.num_leaf = 1
        while self.num_leaf < n:
            self.num_leaf *= 2
        self.data = [default] * (2*self.num_leaf)
        self.f = f

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

    # return f(a[l:r])
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1: # l % 2 == 1
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1: # r % 2 == 0
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1 # l //= 2
            r >>= 1 # r //= 2
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            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.num_leaf
        while self.data[x] < v:
            if x & 1: # x % 2 == 1
                if len(bin(x)) == len(bin(x+1)):
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

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

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

    st = SegmentTree(n=n, f=max, default=-1)
    for i, ai in enumerate(a):
        st.update(i, ai)

    ans = []
    for _ in range(q):
        t, x, v = map(int, input().split())
        if t == 1:
            st.update(x-1, v)
        elif t == 2:
            ans.append(st.query(x-1, v))
        else:
            ans.append(min(st.lower_bound(x-1, v), n) + 1)
    
    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import add
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            pre = self.intv
            for idx in (SR + SL[::-1]):
                if check(self.segf(self.data[idx], pre)):
                    break
                else:
                    pre = self.segf(self.data[idx], pre)
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(self.data[2*idx+1], pre)):
                    idx = 2*idx + 1
                else:
                    pre = self.segf(self.data[2*idx+1], pre)
                    idx = 2*idx
            return idx - self.N0
        else:
            pre = self.intv
            for idx in (SL + SR[::-1]):
                if not check(self.segf(pre, self.data[idx])):
                    pre = self.segf(pre, self.data[idx])
                else:
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(pre, self.data[2*idx])):
                    idx = 2*idx
                else:
                    pre = self.segf(pre, self.data[2*idx])
                    idx = 2*idx + 1
            return idx - self.N0


N, Q = map(int, readline().split())
A = list(map(int, readline().split()))
INF = 10**9+7
T = Segtree(A, -INF, initialize = True, segf = max)
Ans = []
N0 = T.N0
for _ in range(Q):
    t, x, v = map(int, readline().split())
    if t == 1:
        T.update(x-1, v)
    elif t == 2:
        Ans.append(T.query(x-1, v))
    else:
        k = T.binsearch(x-1, N0, lambda x: x >= v)
        if k == -1:
            Ans.append(N+1)
        else:
            Ans.append(k+1)

print('\n'.join(map(str, Ans)))

Submission status: Accepted

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

# SegmentTree
class SegmentTree:
  def __init__(self,n,p,unit,f):
    self.num=2**((n-1).bit_length())
    self.seg=[unit]*(2*self.num)
    for i in range(n):self.seg[i+self.num]=p[i]
    for i in range(self.num-1,0,-1):
      self.seg[i]=f(self.seg[i<<1],self.seg[(i<<1)+1])
    self.f=f
    self.unit=unit
  def update(self,i,x):
    i+=self.num
    self.seg[i]=x
    while i:
      i>>=1
      self.seg[i]=self.f(self.seg[i<<1],self.seg[(i<<1)+1])
  def query(self,l,r):
    ansl=ansr=self.unit
    l+=self.num
    r+=self.num-1
    if l==r:
      return self.seg[l]
    f=self.f
    while l<r:
      if l&1:
        ansl=f(ansl,self.seg[l])
        l+=1
      if ~r&1:
        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)


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)
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:
mod = 1000000007
eps = 10**-9


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

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

        # return smallest i(l <= i < r) s.t. check(A[i]) == True
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1

    def check(val):
        return val >= v

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

    ST = SegmentTree(A, segfunc=max, ident=-2000000000)
    for _ in range(Q):
        t, x, v = map(int, input().split())
        if t == 1:
            ST.update(x, v)
        elif t == 2:
            l = x
            r = v+1
            print(ST.query(l, r))
        else:
            print(ST.binsearch(x, N+1, check))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=max  # 関数
    condition=lambda self,a,b: a>=b # max_right用に定義
    def __init__(self,n,seq): # 元のseqと要素数n
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n): # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def get(self, i): # 値を入手
        return self.x[i+self.n] 
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)
    def max_right(self, l, v): 
        # index lを含めて右にある値の中でa[j]>=vを満たす最小のindexを求める
        # 存在しない場合はnを出力
        r=self.n
        if self.condition(self.fold(l,r),v)==False:
            return r
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.condition(self.fold(l1, r1),v)==True:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return l
    def min_left(self, r, v): 
        # index rを含まずに左にある値の中でa[j]>=vを満たす最大のindexを求める
        # 存在しない場合は0を出力
        l=0
        if self.condition(self.fold(l, r),v)==False:
            return l
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.condition(self.fold(l1, r1),v)==True:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return r

n,q=map(int,input().split()) 
*a,=map(int,input().split())
seg=segtree(n,a)


for i in range(q):
    t,x,y=map(int,input().split()) 
    if t==1:
        x-=1
        seg.update(x, y)
    elif t==2:
        print(seg.fold(x-1,y))
    else:
        print(seg.max_right(x-1, y)+1)