بیشینه در آرایه متغیر

Main.py

import math
MAX_N = 100010
mx = [0] * MAX_N

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

for i in range(n):
    mx[int(i/T)] = max(mx[int(i/T)], a[i]) # mx[x] = max(a[x*T] ... a[(x+1)*T-1]

for i in range(q):
    inp = list(map(int ,input().split()))
    queryType = inp[0]
    if queryType == 1:
        L = inp[1]
        R = inp[2]
        result = 0
        cur = L
        # result = max : a[L] ... , a[k-1] , mx[k/T], mx[k/T+1], ... mx[(k+s)/T], a[k+s], ..., a[R-1]
        while cur <= R :
            if (int(cur / T) * T == cur and cur + T <= R):
                result = max(result, mx[int(cur / T)]);
                cur += T;
            else :
                result = max(result, a[cur]);
                cur += 1;
        print(result)
    else:
        idx = inp[1]
        nv = inp[2]
        mx[int(idx/T)] = 0
        a[idx] = nv
        # update mx
        # only mx[int(idx/T)] changes
        for i in range(int(idx / T) * T, min(n, int(idx / T + 1) * T)):
            mx[int(idx/T)] = max(mx[int(idx/T)], a[i])