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_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+1,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(1,x,1)>=beta)
        if Y==None:
            X.append(N+1)
        else:
            X.append(Y)

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

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+1,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(0,x,1)>=beta)
        if Y==None:
            X.append(N+1)
        else:
            X.append(Y)

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

Submission status: Time Limit Exceeded

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<self.len-1:
      xl,xr=xl*2+1,xr*2+2
    if xr<l+self.len-1 or r+self.len-1<xl:
      return self.init_value
    elif l+self.len-1<=xl and xr<=r+self.len-1:
      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: Time Limit Exceeded

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 search_left(self,f,L,R):
      if not f(self.fold(L,R)): return R
      while R-L>1:
        M = (R+L)//2
        if f(self.fold(L,M)): R = M
        else: L = M
      return L

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:
    print(seg.search_left(lambda x: x >= b,a-1,N)+1)

Submission status: Time Limit Exceeded

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


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 find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.e
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            res = self.func(find_l, find_r)
            return res

    def count(self, l, r):
        return self.find(l-1, r, 0, 0, self.size-self.N)
    
    def bisect_sub(self, a, b, k, l, r, x):
        if r <= a or b <= l:
            return b+1
        elif self.segment[k] < x:
            return b+1
        elif k >= self.N:
            return r
        else:
            find_l = self.bisect_sub(a, b, 2*k+1, l, (l+r)//2, x)
            find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
            res = min(find_l, find_r)
            return res

    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: Time Limit Exceeded

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

def solve():
    N,Q = map(int,input().split())
    A = list(map(int,input().split()))
    qs = [tuple(map(int,input().split())) for i in range(Q)]

    class SegTree:
        def __init__(self,arr,func,unit):
            self.func = func
            self.unit = unit
            n = 1
            while n < len(arr):
                n *= 2
            self.n = n
            nodes = [unit]*(2*n-1)
            nodes[n-1:n-1+len(arr)] = arr
            for i in range(n-2,-1,-1):
                nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
            self.nodes = nodes

        def update(self,i,val):
            i += self.n-1
            self.nodes[i] = val
            while i >= 0:
                i = (i - 1) // 2
                self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

        def query(self,l,r):
            l += self.n
            r += self.n
            s = self.unit
            while l < r:
                if r & 1:
                    r -= 1
                    s = self.func(self.nodes[r-1], s)
                if l & 1:
                    s = self.func(s, self.nodes[l-1])
                    l += 1
                l >>= 1
                r >>= 1
            return s

    INF = float('inf')
    segt = SegTree(A, lambda x,y:max(x,y), -INF)

    ans = []
    for a,b,c in qs:
        if a==1:
            segt.update(b-1,c)
        elif a==2:
            ans.append(segt.query(b-1,c))
        else:
            l = b-1
            r = N
            if segt.query(l,r) < c:
                ans.append(N+1)
            else:
                while r-l > 1:
                    m = (l+r)//2
                    if segt.query(l,m) >= c:
                        r = m
                    else:
                        l = m
                ans.append(r)
    print(*ans, sep='\n')
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
A = list(map(int,input().split()))
qs = [tuple(map(int,input().split())) for i in range(Q)]

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

INF = float('inf')
segt = SegTree(A, lambda x,y:max(x,y), -INF)

ans = []
for a,b,c in qs:
    if a==1:
        segt.update(b-1,c)
    elif a==2:
        ans.append(segt.query(b-1,c))
    else:
        l = b-1
        r = N
        if segt.query(l,r) < c:
            ans.append(N+1)
        else:
            while r-l > 1:
                m = (l+r)//2
                if segt.query(l,m) >= c:
                    r = m
                else:
                    l = m
            ans.append(r)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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]=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]
    while l<r:
      if l&1:
        ansl=self.f(ansl,self.seg[l])
        l+=1
      if ~r&1:
        ansr=self.f(self.seg[r],ansr)
        r-=1
      l>>=1
      r>>=1
    if l==r:
      ansl=self.f(ansl,self.seg[l])
    return self.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: Time Limit Exceeded

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(X - 1, 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: Time Limit Exceeded

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

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

num = 2**(n-1).bit_length()
def segfunc(x, y): return max(x, y)
seg = [0]*(2*num-1)
for i in range(n):
  seg[i+num-1] = a[i]
for i in range(num-2, -1, -1):
  seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
def update(i, x):
  i += num-1
  seg[i] = x
  while i:
    i = (i-1)//2
    seg[i] = segfunc(seg[i*2+1], seg[i*2+2])
def query(l, r):
  l += num-1
  r += num-2
  if l == r:
    return seg[l]
  s = seg[l]
  l += 1
  while r-l > 1:
    if ~l % 2:
      s = segfunc(seg[l], s)
    if r % 2:
      s = segfunc(seg[r], s)
      r -= 1
    l //= 2
    r = (r-1)//2
  if l == r:
    return segfunc(s, seg[l])
  return segfunc(s, segfunc(seg[l], seg[r]))

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

Submission status: Time Limit Exceeded

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

num = 2**(n-1).bit_length()
def segfunc(x, y): return max(x, y)
seg = [0]*(2*num-1)
for i in range(n):
  seg[i+num-1] = a[i]
for i in range(num-2, -1, -1):
  seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
def update(i, x):
  i += num-1
  seg[i] = x
  while i:
    i = (i-1)//2
    seg[i] = segfunc(seg[i*2+1], seg[i*2+2])
def query(l, r):
  l += num-1
  r += num-2
  if l == r:
    return seg[l]
  s = seg[l]
  l += 1
  while r-l > 1:
    if ~l % 2:
      s = segfunc(seg[l], s)
    if r % 2:
      s = segfunc(seg[r], s)
      r -= 1
    l //= 2
    r = (r-1)//2
  if l == r:
    return segfunc(s, seg[l])
  return segfunc(s, segfunc(seg[l], seg[r]))

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class SegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

seg = SegTree(N + 1, -1, [-1] + a)
for _ in range(Q):
  t, x, v = map(int, input().split())
  if t == 1: seg.update(x, v)
  if t == 2: print(seg.query(x, v + 1))
  if t == 3:
    ok = N + 1
    ng = x - 1
    while ok - ng > 1:
      m = (ok + ng) // 2
      if seg.query(x, m + 1) >= v: ok = m
      else: ng = m
    print(ok)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        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])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        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):
        """[l,r) が ok であるような最大の r を返す"""
        if l == self.n:
            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.n

    def min_left(self, r, x):
        """(r が ok であるような最小の r を返す"""
        if r == 0:
            return 0
        r += self.size
        res = self.sta
        check = True
        while check and (r & -r) != r:
            check = False
            r -= 1
            while (r > 1 and r%2):
                r >>= 1
            if not self.func(res, self.tree[r]) < x:
                while r < self.size:
                    r = 2*r + 1
                    if self.func(res, self.tree[r]) < x:
                        res = self.func(res, self.tree[r])
                        r -= 1
                return r + 1 - self.size
            res = self.func(self.tree[r],res)
        return 0

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

seg = SegTree(n,max,-1)
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: Accepted

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

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

    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.n:
            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.n

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)