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

        d=max(1,(N-1).bit_length())
        k=2**d

        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==r:
            return r+index

        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

            m=l+1
            if not (m&(-m) !=m):
                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),-1,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: Accepted

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

        d=max(1,(N-1).bit_length())
        k=2**d

        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==r:
            return r+index

        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

            m=l+1
            if not (m&(-m) !=m):
                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: Accepted

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

        d=max(1,(N-1).bit_length())
        k=2**d

        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==r:
            return r+index

        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

            m=l+1
            if not (m&(-m) !=m):
                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),0,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: Accepted

Solution code:
import sys
from operator import ge

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class SegTree:
    """
    セグメント木
    1.update: i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def add(self, i, x):
        self.update(i, self.get(i) + x)

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def bisearch_fore(self, l, r, x, func):
        """ 区間[l,r]で左から最初にxに対して比較の条件を満たすような値が出現する位置 """

        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if func(self.query(l, mid+1), x):
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x, func):
        """ 区間[l,r]で右から最初にxに対して比較の条件を満たすような値が出現する位置 """

        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if func(self.query(mid, r+1), x):
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = LIST()
seg = SegTree(N, max, -INF, A)

for _ in range(Q):
    t, a, b = MAP()

    if t == 1:
        a -= 1
        seg.update(a, b)
    elif t == 2:
        a -= 1; b -= 1
        res = seg.query(a, b+1)
        print(res)
    else:
        a -= 1
        res = seg.bisearch_fore(a, N-1, b, ge)
        if res == INF:
            print(N+1)
        else:
            print(res+1)

Submission status: Accepted

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)

    class SegmentTree:
        def __init__(self, init_val, ide_ele):
            self.n = len(init_val)
            self.ide_ele = ide_ele
            self.num = 2 ** (self.n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            for i in range(self.n):
                self.seg[i + self.num - 1] = init_val[i]

            for i in range(self.num - 2, -1, -1):
                self.seg[i] = 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:
                k = (k - 1) // 2
                self.seg[k] = 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 = segfunc(res, self.seg[p])
                if q & 1 == 1:
                    res = segfunc(res, self.seg[q])
                    q -= 1
                p = p // 2
                q = (q - 1) // 2
            if p == q:
                res = segfunc(res, self.seg[p])
            else:
                res = segfunc(segfunc(res, self.seg[p]), self.seg[q])
            return res

    s = SegmentTree(A, 0)

    def isOK(mid, m, value):
        a = s.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:
            s.update(X - 1, V)
            B[X - 1] = V
        elif T == 2:
            print(s.query(X - 1, V))
        else:
            a = s.query(X - 1, N)
            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: Accepted

Solution code:
#参照https://atcoder.jp/contests/practice2/submissions/16580070 
class SegmentTree:
 
    __slots__ = ["func", "e", "original_size", "n", "data"]
 
    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * self.n
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + [self.e] * (self.n - self.original_size)
            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):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            # l //= l & -l
            while l % 2 == 0:
                l //= 2
            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
            if l == l & -l:
                break
        return self.original_size
 
    # 未verify
    def min_left(self, r, f):
        # assert f(self.e)
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            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 = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n 
            if r == r & -r:
                break
        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, 0)
    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(seg.max_right(X-1, lambda a: a < V)+ 1)
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
code = r"""
#include <atcoder/segtree>
#include <cstdio>
#include <vector>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return max(a, b); }

int e() { return -1; }

int target;

bool f(int v) { return v < target; }

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &(a[i]));
    }

    segtree<int, op, e> seg(a);

    for (int i = 0; i < q; i++) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x, v;
            scanf("%d %d", &x, &v);
            x--;
            seg.set(x, v);
        } else if (t == 2) {
            int l, r;
            scanf("%d %d", &l, &r);
            l--;
            printf("%d\n", seg.prod(l, r));
        } else if (t == 3) {
            int p;
            scanf("%d %d", &p, &target);
            p--;
            printf("%d\n", seg.max_right<f>(p) + 1);
        }
    }
}
"""
import os
import sys
op = open("in.txt", "wt")
while True:
    try:
        op.write(input()+"\n")
    except EOFError:
        break
op.close()
open('a.cpp', 'w').write(code)
os.system('g++ -I /opt/atcoder-stl a.cpp')
os.system('./a.out < in.txt > out.txt')
op = open("out.txt", "r")
while True:
    tmp = op.readline()
    if tmp:
        print(tmp, end='')
    else:
        break
op.close()

Submission status: Accepted

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-1] >= x:
                    Rmin = r-1
            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: Accepted

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 - 1)
        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: Accepted

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