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 SegmentTree:
    def __init__(self, n, func=lambda x, y : max(x, y), default_val = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [default_val] * self.node_n
        self.default_val = default_val
        self.f = func

        if init_list:
            self.tree[self.offset:self.offset+n] = init_list
            self.update_all()
    
    def set_values(self, val_list):
        n = len(val_list)
        assert self.leaf_n >= n
        self.tree[self.offset:self.offset+n] = val_list
    
    def set_value(self, index, val):
        assert 0 <= index < self.leaf_n
        self.tree[self.offset+index] = val

    def get_value(self, index):
        assert 0 <= index < self.leaf_n
        return self.tree[self.offset + index]

    def update_all(self):
        l = self.offset
        n = self.leaf_n
        while l > 0:
            for i in range(l, l + n, 2):
                self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            l >>= 1
            n >>= 1

    def update(self, index, val):
        assert 0 <= index < self.leaf_n
        i = self.offset + index
        self.tree[i] = val
        while i > 0:
            if i & 1 == 0:
                i -= 1
            self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            i >>= 1
    # 閉区間 [l, r] の演算結果
    def query(self, l, r):
        assert 0 <= l <= r < self.leaf_n
        left_val = self.default_val
        right_val = self.default_val
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.default_val))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.default_val
        while True:
            while i & 1 != 0: # iを左端とする最上の層まで移動
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #iを左端とする1個下の層に移動
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1

    def search_min_left(self, r, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の l を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x): x <= v
        '''
        assert(0 <= r < self.leaf_n and check_func(self.default_val))
        i = r + self.offset
        if not check_func(self.tree[i]):
            return -1
        right_val = self.default_val
        while True:
            while i & 1 == 0 and i > 0: # iを右端とする最上の層まで移動
                i = (i - 1) >> 1
            x = self.f(self.tree[i], right_val)
            if not check_func(x):
                while i < self.offset:
                    i = (i + 1) << 1 #iを右端とする1個下の層に移動
                    x = self.f(self.tree[i], right_val)
                    if check_func(x):
                        right_val = x
                        i -= 1
                return i - self.offset + 1
            right_val = x
            if i & (i + 1) == 0:
                return 0
            i -= 1

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

st = SegmentTree(n, max, 0, a)
ans = []
for _ in range(q):
    t, x, v = map(int, input().split())
    if t == 1:
        st.update(n-x, v)
    elif t == 2:
        ans.append(st.query(n-v, n-x))
    else:
        if v == 0:
            ans.append(x)
        else:
            i = st.search_min_left(n - x, lambda y: y < v)
            if i < 0:
                ans.append(x)
            else:
                ans.append(n - i + 1)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, func=lambda x, y : max(x, y), default_val = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [default_val] * self.node_n
        self.default_val = default_val
        self.f = func

        if init_list:
            self.tree[self.offset:self.offset+n] = init_list
            self.update_all()
    
    def set_values(self, val_list):
        n = len(val_list)
        assert self.leaf_n >= n
        self.tree[self.offset:self.offset+n] = val_list
    
    def set_value(self, index, val):
        assert 0 <= index < self.leaf_n
        self.tree[self.offset+index] = val

    def get_value(self, index):
        assert 0 <= index < self.leaf_n
        return self.tree[self.offset + index]

    def update_all(self):
        l = self.offset
        n = self.leaf_n
        while l > 0:
            for i in range(l, l + n, 2):
                self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            l >>= 1
            n >>= 1

    def update(self, index, val):
        assert 0 <= index < self.leaf_n
        i = self.offset + index
        self.tree[i] = val
        while i > 0:
            if i & 1 == 0:
                i -= 1
            self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            i >>= 1
    # 閉区間 [l, r] の演算結果
    def query(self, l, r):
        assert 0 <= l <= r < self.leaf_n
        left_val = self.default_val
        right_val = self.default_val
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.default_val))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.default_val
        while True:
            while i & 1 != 0: # iを左端とする最上の層まで移動
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #iを左端とする1個下の層に移動
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1

    def search_min_left(self, r, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の l を返す。
        -------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x): x <= v
        '''
        assert(0 <= r < self.leaf_n and check_func(self.default_val))
        i = r + self.offset
        if not check_func(self.tree[i]):
            return -1
        right_val = self.default_val
        while True:
            while i & 1 == 0 and i > 0: # iを右端とする最上の層まで移動
                i = (i - 1) >> 1
            x = self.f(self.tree[i], right_val)
            if not check_func(x):
                while i < self.offset:
                    i = (i + 1) << 1 #iを右端とする1個下の層に移動
                    x = self.f(self.tree[i], right_val)
                    if check_func(x):
                        right_val = x
                        i -= 1
                return i - self.offset + 1
            right_val = x
            if i & (i + 1) == 0:
                return 0
            i -= 1

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

st = SegmentTree(n, max, 0, a)
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-1))
    else:
        if v == 0:
            ans.append(x)
        else:
            i = st.search_max_right(x - 1, lambda y: y < v)
            ans.append(x if i < 0 else i + 2)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ng = x
        ok = n+1
        while ok - ng > 1:
            mid = (ok+ng)//2
            if seg.fold(x, mid) >= v:
                ok = mid
            else:
                ng = mid
        print(ok)

Submission status: Accepted

Solution code:
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ng = x
        ok = n+1
        while ok - ng > 1:
            mid = (ok+ng)//2
            if seg.fold(x, mid) >= v:
                ok = mid
            else:
                ng = mid
        print(ok)

Submission status: Accepted

Solution code:
class RMaxQ:
    
    __slots__ = ["n", "data"]
    
    def __init__(self, li):
        self.n = len(li)
        self.data = li*2
        for i in range(self.n - 1, 0, -1):
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l < r:
            if l % 2:
                res = max(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

n, q = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
    t, x, v = map(int, input().split())
    x -= 1
    if t == 1:
        seg.update(x, v)
    elif t == 2:
        print(seg.fold(x, v))
    else:
        ng = x
        ok = n+1
        while ok - ng > 1:
            mid = (ok+ng)//2
            if seg.fold(x, mid) >= v:
                ok = mid
            else:
                ng = mid
        print(ok)

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$}SA&2Hm15WWY<I}lj3krE|{7kgL)ac-Mq_tINx2(m=mglS4k%ig571ikgvK0t5np+H~Cmp;bMkQ7CcRDM=4V3EW5`{v__d`HTMc2$cjGOu@{+LkL?uBW#J-_qlwg{(J5ez9ltD=FEgsbxzFDT@aq=WJeHY}*R{t$b5(UY8kJND5|-kIMF;p%q;aUW+A3PCundN<_V6Jd}M-6MW0mI9$a<3yW^`A}fXkC@gug-I6U`w&3{c_=vz$c3Qc}$d>&|(el!fp`lY!IWwOKbw-~_-Jl1Yz;T|JOt3c36XOUR@<nRg;qy~1D0xQ?kAJG)KZmE^4o|-y9{)Q${qg_5e;=M6508I!CY6tU%_@Rc2R1VmH-wELWEhs~#Rh+OH6wd6)m2Fnk)=A(dZ9te$O%75Jw>$4K<Tod|H|5x2GsGQ1S`fVtiC3~li;(zV>2*BlQfhuayBKCejc;BQ0SqvTt~dmRC+XxL*gzSqGOYH5ehP}=?aLFQ<3arSO6zHG*r?Pa(%62VeU9P%+4A^^ub!E9H|*OZD7H*e!VdpCV5XzweIPlfUl{YEm3E~i?$i5l3$@wyMFr3or?5~D7#34=MAgU=U4;bO&YZD&y(n)3=mZF70fo?9GdX;YXrG&hS@21=Wb|Sk~a{rm!*z6-!)ayQrPk=fbU#o>9&W8s%k#dAh0hcI+F<Lw=~uU8qIfdA2Pf_s4bK}R(A~+=zfGl5g4wg7X25{XvobC2_ZRiAn6&ujHeZ*BWb&n!bT4iv$@SevyH5)h+VG#<VZhIs@n}GCRf-O&@?yF8TT4|1YbEauYu&SX`}}r1JC5gfMp8XKA5^mV3c(T@L8m@a&LPX>vF`pG&~KxO4qA)C}#=_&nt&w2R5WX=@!rCp=|kugH4hL#e0bjlOY4J#GB$imu$I;u?w8vl88}Nhv~FyN*-XY%Urz71D8=z0%=10EO&la?wA5a!*DJmm5ag-@r$}8i=@ZdrAr#I)05I>5Lu-?PSsb0$Hn0LEq=SFhbB-PSBkM5A5$R?eLPZ+H@O?xNLZ6|#S#BBgwI^kVjbrw62@mJ6FH}g7(wMYL1l~)#*_1f9&1A1Ps&)Y(2HTW15pc6J=14i#a6e^Ji}J`3bsnaR=^>~6yyIbzPo2gp@G`C(paN4g;P<!mbK5gG_C$zk;MPX;1g%)Wq8_fKIb7l*C8`aRO?w7DVAY9vs+CKG2fZ${_btEDI~Oi%I%G@k%d@N?@GyPD~H2Fxhi0{G!o)k*c%@P3D>b?7^fA@Gg9^kT63g#l9_|hn0B`YpgRZZefW6g<A~Nu$ZK*5iOr#qA3kcK0l2i0sjY|KCh7%eR-R8TyC>8EO!YU?9Qx)%6A)hkTX7zKCJQ}7;r<>9=L6XE<-#wqS-OVw_k-nla#u)a<V*j`GSX&bm*L{Ug|v9Zg>+F%I4v?^st*fwDAP%LMGAdkQGSf=o}WuaJ~cuqyau;QfKDT+|7pbE7ssE@zU@8Ya5o(8heN1Bi`#E9*d5CYJiqVoh5@LgT|K(R@7;5|;&O8G1FwD&Cz(=KCnBqzM$2jSdbR!#WOU)10y_`%zX3Jegro")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$}SA&2Hm15WWY<I}li`BRO&q?=i4*+Z?->-cm!5CE6BDQwk+}lim{a)?51ky|sq|eJNl17@Z+0i6SY-DPceshx7N%#}WC7q%ZZR;CEzM?0HtD8=7wC4+*R2<;6-AJ1xIC<n%j9^Ichpnj}IbFIvv>WqMQ989ZD0E@7-lBeD_{%v@fi^-D=Jx+1LLYZ8pVhCxVpvCf$*`xXZHFOu)>s+`xb=s_)N#jpT{DNCw~RCHZ~<GafX0wZm-Vjhty|CyrYwIM@8W0Dy&UkNqdzLBCt4>*DEah&Enuj4q-j=&*Xh1wmC9|}&%CvtrKUH<+$zWs81`}O$x&++ZIfB*jT`1X2y{i87{eH@BBBWSf}Gm>#b*cd{DVVPdq;2-Z6<Ur=CDnY=bP$gQd6i5-dVppN1h?a9uy6xt_=k-PbYIu=?P0lE+o)K<Ia2y`<1sI}1=*n_(Jtxy{9<#cU=%KS%MSO^4dNlMyVlM5Y(<W~s<YdsM%OOfed2sMy0i3YVkV#L;Y$j!H?l{}et~G|}gSAH4Q!_FyVZluOz1JHi_(H}?cib!BIkjs`)Y!11EeEP(S7^|#oqqW!BfTclE|TE1VOjbZYrw5ZjTSyEi7HADK{=nnY-!D*30uEFkc+aPopd)bLu-<}hk&gtRn+mm%#xbImd_pdCNfL2J!Di?^F)Kdz8I)XJfyFvuML!n@8sEKc!^NAP}*2MmRO+Y0S<X!n9W=C-$A1!_xHqw<l2CwWBl5mmYa^C^<MBcdZ1XF+rl+liX!vaW$GaY`hirfc8us;VP8Pg+zI2o(_jPmih+3rB!f*OEC6%xOhyjNB(_~JMH#?b)F8kXp3cgw?WL`Y0qa8Z)b%P%ugalVNGvR`42td85cZ^5yfzPM%Pt&jlGrKUdu*8Y8Gt3;CC{<Q*Bc+Z!1)957?pLH&zq)X0cN_4`TIOD8RaFABE*kkZ+GQ}DNr;F=hjm>FYFLMFKV(1I-E_qgdRH`DccM@tCYvN{E9HY7<_-kZ!<b*9JOI3AIov*3Nh&8o_c)9-M~h|noJ}|?9&jArJ%{y&ru|d&Cs03jIMkH6~hD-K1OIy#us|13H^Uk`g(<047(kOn(*vIpE--IW}i91R&fSfg=Q<@;A4vR{}JEK=u@btHmo$%Xm#Oal;^VcgiGD(Cz2%gR|bclp||d7!}y%L^xV44)KP60ZlqX-?V{ak@)h%4$nJ06Cd))X`=_kEF_t3XYieC7^P-hkX~H3<Qb1Iz_P!_Sjs2en{XliPlj&_UTpfs8eTVeHYS}jd2q!@IrTZyL)C`3?vMXG+ju1a}fVW}POSi!8LvJ};^_~Fuh}03;M<|qe2Unl7&)HQ(MzCP?6dIY}^(Q&w?zbug9L#dAfrf=DqWQGh0gWdn9VKv{Z~Sz$Sj(ErH|!+v*SX9AnhIR?q#oZ-gTAvSPso1+0F0We8Wf{OrcZlBT;JePd5?#A04r?D(k%XB9+4$+WO_gGt4J!#!$+$fdaK&%b!y#tL+e8O29ksRfBN!b-2")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(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 = [ide_ele]*(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.ide_ele
            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.ide_ele
                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 None
                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.ide_ele
                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 None
                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=MI()
    A=LI()
    seg=Segtree(A,0,segf=max)
    N0=seg.N0
    for _ in range(Q):
        t,x,v=MI()
        if t==1:
            x-=1
            seg.update(x,v)
        elif t==2:
            l=x-1
            r=v
            print(seg.query(l,r))
        else:
            l=x-1
            r=N
            ans=seg.binsearch(l,r,lambda x: x>=v)
            if ans==None:
                ans=N
            
                
            print(ans+1)
    
    

 
 


        
    





main()

Submission status: Accepted

Solution code:
# 一点更新区間取得
class segmentTree:
    def __init__(self, init_val, operator, identity):
        """
        :param init_val: 操作したい配列
        :param operator: 演算子(minはそのままでok。sumはlistを引数にとるからエラー->add関数を自作)
        :param identity: 演算子に対応する単位元(minならinf,sumなら0)
        """
        self.identity = identity
        self.operator = operator

        n = len(init_val)
        n_bin = bin(n)[2:]
        bc = sum([int(digit) for digit in n_bin])
        if bc == 1:  # 2のべき乗ならすっぽり入る
            self.num_end_leaves = 2**(len(n_bin)-1)
        else:  # 2のべき乗でないなら、はみ出すからー１しない
            self.num_end_leaves = 2**len(n_bin)

        self.tree = [identity for _ in range(self.num_end_leaves * 2)]
        # 葉に要素をセット
        for i in range(n):
            self.tree[i + self.num_end_leaves] = init_val[i]
        # segtree構築
        for i in range(1, self.num_end_leaves)[::-1]:
            self.tree[i] = self.operator(self.tree[2*i], self.tree[2*i+1])


    def update(self, x, val):
        """
        :param x: 更新するidx(0-indexed)
        :param val: 更新する値
        """
        leaf_x = x + self.num_end_leaves
        self.tree[leaf_x] = val
        while leaf_x > 0:
            leaf_x //= 2
            self.tree[leaf_x] = self.operator(self.tree[leaf_x*2], self.tree[leaf_x*2+1])
            # operaterがminだったりする

    def query(self, left, right):
        """
        :param left: queryの左idx(1-indexed)
        :param right: queryの右idx(1-indexed)
        大体queryは1-indexedなので、0-indexedにして
        left_0 = left - 1
        right_0 = right - 1
        半閉半開を考えるので、[left_0, right_0+1)
        つまり、[left_0, right)
        leftだけ-1する
        """
        left += self.num_end_leaves
        left -= 1
        right += self.num_end_leaves
        val_l = val_r = self.identity
        while right - left > 0:
            if left & 1:
                val_l = self.operator(val_l, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                val_r = self.operator(self.tree[right], val_r)
            left >>= 1
            right >>= 1
        return self.operator(val_l, val_r)


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.update(x - 1, y)
    elif t == 2:
        print(st.query(x, y))
    else:
        hi = n + 1
        lo = x - 1
        while hi - lo > 1:
            mid = (hi + lo) // 2
            if st.query(x, mid) >= y:
                hi = mid
            else:
                lo = mid
        print(lo + 1)

Submission status: Accepted

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


def solve():
    def init(init_arr):
        global num, segfunc, ide_ele, seg
        segfunc = lambda x, y: max(x, y)
        ide_ele = 0
        num = 2 ** (n - 1).bit_length()
        seg = [ide_ele] * 2 * num
        for i in range(n):
            seg[i + num - 1] = init_arr[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

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

    init(a)
    res = []

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


solve()

Submission status: Accepted

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


def solve():
    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

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

    segfunc = lambda x, y: max(x, y)
    ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    init(a)
    res = []

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


solve()

Submission status: Accepted

Solution code:
def solve():
    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

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

    ide_ele = 0

    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(a)

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


solve()

Submission status: Accepted

Solution code:
# セグ木ソラ書き練習
# 10分くらい
# query()でバグらせたので反省
import sys
input = lambda: sys.stdin.readline().rstrip()

class SegmentTree:
    def __init__(self,n,p,unit,f):
        self.num=2**((n-1).bit_length())
        self.seg=[unit]*(self.num*2)
        for i in range(n):
            self.seg[self.num+i]=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.unit=unit
        self.f=f
    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]
        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)