提出 #73259257

---

ソースコード 拡げる

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())
mod = 10**9+7
inf = 1<<60
class SparseTable:
    # 时间复杂度 O(n * log n)
    def __init__(self, nums, op):
        n = len(nums)
        w = n.bit_length()
        st = [[0] * n for _ in range(w)]
        st[0] = nums[:]
        for i in range(1, w):
            for j in range(n - (1 << i) + 1):
                st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))])
        self.st = st
        self.op = op

    # [l, r) 左闭右开，下标从 0 开始
    # 返回 op(nums[l:r])
    # 时间复杂度 O(1)
    def query(self, l: int, r: int) -> int:
        k = (r - l).bit_length() - 1
        return self.op(self.st[k][l], self.st[k][r - (1 << k)])
def solve():
    n,q = mii()
    a = lii()
    st = SparseTable(a,max)
    for i in range(q):
        l,r = mii()
        print(st.query(l-1,r))

t = 1
# t = ii()
for _ in range(t):
    solve()

提出情報

ジャッジ結果