14_st.py

class ST:
    def build(self, arr):
        max_len = 4 * len(arr)
        self.st = [None] * max_len
        self.arr_len = len(arr)
        self.helper(arr, 1, 0, len(arr) - 1)
    
    def helper(self, arr, v, l, r):
        if l == r:
            self.st[v] = arr[l]
            return
        m = (l + r) // 2
        self.helper(arr, v * 2, l, m)
        self.helper(arr, v * 2 + 1, m + 1, r)
        self.st[v] = max(self.st[v * 2], self.st[v * 2 + 1])
    
    def find(self, l_obj, r_obj):
        return self.find_helper(1, 0, self.arr_len - 1, l_obj, r_obj)

    def find_helper(self, v, l, r, l_obj, r_obj):
        if l_obj > r_obj:
            return -10**6
        if l == l_obj and r == r_obj:
            return self.st[v]

        ml = (l + r) // 2
        mr = (l + r) // 2 + 1
        while True:
            if r_obj < ml:
                v = v * 2
                r = ml
                ml = (l + r) // 2
                mr = ml + 1
            elif l_obj > mr:
                v = v * 2 + 1
                l = mr
                ml = (l + r) // 2
                mr = ml + 1
            else:
                break
        
        result1 = self.find_helper(v * 2, l, ml, l_obj, ml)
        result2 = self.find_helper(v * 2 + 1, mr, r, mr, r_obj)
        return max(result1, result2)

class Solution:
    def solve(self, nums, k):
        result = []
        st = ST()
        st.build(nums)
        for i in range(len(nums) - k + 1):
            result.append(st.find(i, i + k - 1))
        return result

import time
from nums_len_50000 import nums, ans
from nums2 import nums2, ans2
k = 654
k2 = 33123
s = Solution()
start = time.time()
# st = ST()
# st.build([3, 3, 3, 3, 3, 3, 3, 2, 1])
# assert st.find(6, 8) == 3
assert s.solve([3, 3, 3, 3, 3, 3, 3, 2, 1], 3) == [3, 3, 3, 3, 3, 3, 3]
assert s.solve([1, 2, 3, 4, 5, 4, 3, 2, 1], 3) == [3, 4, 5, 5, 5, 4, 3]
assert s.solve(nums, k) == ans
assert s.solve(nums2, k2) == ans2
end = time.time()
print(end - start)