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 .

Solution (Python):



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):
        
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            l //= l & -l
            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

    
    def min_left(self, r, f):
        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, -1)
    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(min(N, seg.max_right(X-1, lambda a: a < V)) + 1)


if __name__ == "__main__":
    main()

Solution (Python):
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]*(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)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)




def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    global WIDTH
    WIDTH = width
    set_depth((width - 1).bit_length() + 1)


def point_set(table, pos, value, binop):
    pos = pos + NONLEAF_SIZE
    table[pos] = value
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
        )


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def bisect_left(table, left, right, value):
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    left_left = None
    right_left = None
    while left < right:
        if left & 1:
            if left_left is None and table[left] >= value:
                left_left = left
            left += 1
        if right & 1:
            if table[right - 1] >= value:
                right_left = right - 1
        left >>= 1
        right >>= 1

    if left_left is not None:
        pos = left_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    elif right_left is not None:
        pos = right_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    else:
        return WIDTH


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


def main():
    N, Q = map(int, input().split())
    AS = list(map(int, input().split()))
    set_width(N)

    table = [0] * SEGTREE_SIZE
    table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = AS
    full_up(table, max)

    for _q in range(Q):
        q, x, y = map(int, input().split())
        if q == 1:
            
            point_set(table, x - 1, y, max)
        elif q == 2:
            
            print(range_reduce(table, x - 1, y, max, -INF))
        else:
            print(bisect_left(table, x - 1, N, y) + 1)



T1 = """
5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
3
2
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

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


class SegmentTree:

  def __init__(self, n, p, unit, f, g, h):
    num = 2**((n-1).bit_length())
    seg = [unit]*(num*2)
    self.lazy = [None]*(num*2)
    for i in range(n):
      seg[num+i] = p[i]
    for i in range(num-1, 0, -1):
      seg[i] = f(seg[i << 1], seg[(i << 1)+1])
    self.num = num
    self.seg = seg
    self.unit = unit
    self.flag = False
    self.f = f
    self.g = g
    self.h = h

  def gindex(self, l, r):
    l += self.num
    r += self.num
    lm = (l//(l & -l)) >> 1
    rm = (r//(r & -r)) >> 1
    mm = max(lm, rm)
    r -= 1
    while l < r:
      if r <= rm:
        yield r
      if l <= lm:
        yield l
      l >>= 1
      r >>= 1
    while l:
      if l <= mm:
        yield l
      l >>= 1

  def propagates(self, ids):
    num = self.num
    g = self.g
    h = self.h
    for i in reversed(ids):
      v = self.lazy[i]
      if v is None:
        continue
      
      

      newv = (v[0]//2,v[1]//2)

      
      
      if (i << 1) < num:
        self.lazy[i << 1] = h(self.lazy[i << 1], newv)
        self.lazy[(i << 1)+1] = h(self.lazy[(i << 1)+1], newv)
      self.seg[i << 1] = g(self.seg[i << 1], newv)
      self.seg[(i << 1)+1] = g(self.seg[(i << 1)+1], newv)
      self.lazy[i] = None

  def query(self, l, r):
    f = self.f
    if self.flag:
      *ids, = self.gindex(l, r)
      self.propagates(ids)
    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 = f(ansl, self.seg[l])
        l += 1
      if r & 1 == 0:
        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)

  def update1(self, i, x):
    i += self.num
    f = self.f
    self.seg[i] = x
    while i:
      i >>= 1
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])

  def update2(self, l, r, x):
    self.flag = True
    *ids, = self.gindex(l, r)
    self.propagates(ids)
    num = self.num
    f = self.f
    g = self.g
    h = self.h
    l += num
    r += num-1
    if l == r:
      self.seg[l] = g(self.seg[l], x)
      for i in ids:
        self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
      return
    while l < r:
      if l & 1:
        if l < num:
          self.lazy[l] = h(self.lazy[l], x)
        self.seg[l] = g(self.seg[l], x)
        l += 1
      if r & 1 == 0:
        if r < num:
          self.lazy[r] = h(self.lazy[r], x)
        self.seg[r] = g(self.seg[r], x)
        r -= 1
      l >>= 1
      r >>= 1
      x = f(x, x)
    if l == r:
      self.lazy[l] = h(self.lazy[l], x)
      self.seg[l] = g(self.seg[l], x)
    for i in ids:
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
  
  def update(self, i, x):
    if type(i) is int:
      self.update1(i, x)
    else:
      self.update2(i[0], i[1], x)

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

Solution (Python):
class SegmentTree:
    def __init__(self, init_val, segfunc, 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
        self.range = [(-1,n)] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
            self.range[self.num + i] = (i,i)
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
            self.range[i] = (self.range[2 * i][0],self.range[2 * i + 1][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
        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 bisect_l(self,l,r,x):
        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 N

import sys

input = sys.stdin.readline

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

Seg = SegmentTree(A,max,0)

for _ in range(Q):
    query = list(map(int,input().split()))
    if query[0] == 1:
        gomi,idx,val = query
        Seg.update(idx-1,val)
    elif query[0] == 2:
        gomi,l,r = query
        print(Seg.query(l-1,r))
    else:
        gomi,l,val = query
        print(Seg.bisect_l(l-1,N,val)+1)

Solution (Python):
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)

Solution (Python):




import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class SegmentTree:
    def __init__(self, array, function, identify):
        self.length = len(array)
        self.func, self.ide_ele = function, identify

        self.size = 1 << (self.length-1).bit_length()
        self.data = [self.ide_ele] * 2*self.size
        
        for i in range(self.length):
            self.data[self.size + i] = array[i]
        
        for i in range(self.size-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i + 1])

    def update(self, idx, x):
        idx += self.size
        self.data[idx] = x
        while idx > 0:
            idx >>= 1
            self.data[idx] = self.func(self.data[2*idx], self.data[2*idx + 1])
 
    def query(self, l, r):
        l += self.size; r += self.size+1
        l_ret = r_ret = self.ide_ele
        while l < r:
            if l & 1:
                l_ret = self.func(l_ret, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                r_ret = self.func(self.data[r], r_ret)
            l >>= 1; r >>= 1
        return self.func(l_ret, r_ret)

    def get(self, idx):
        return self.data[idx+self.size]

def Main():
    n, q = read_ints()
    a = read_int_list()
    seg = SegmentTree(a, max, -float('inf'))
    for _ in range(q):
        t, x, v = read_ints()
        if t == 1:
            seg.update(~-x, v)
        elif t == 2:
            print(seg.query(~-x, ~-v))
        else:
            l = x - 1; r = n + 1
            while r - l > 1:
                mid = (l + r) // 2
                if seg.query(~-x, ~-mid) >= v:
                    r = mid
                else:
                    l = mid
            print(r)

if __name__ == '__main__':
    Main()