题目描述
给定n个数a[1…n],再给定q个询问,每个询问是一个区间[l, r],对于每个询问,输出a[l…r]的最大值
解题思路
(1)定义f[i][j],表示区间[i, i + 2 ^ j - 1](即从i开始长度为2 ^ j的区间)的最大值。
(2)把该区间分为2个长度为2 ^ (j - 1)的子区间[i, i + 2 ^ (j - 1) - 1]和[i + 2 ^ (j - 1), i + 2 ^ j - 1]
(3)依照对f[i][j]的定义,这两个子区间可以用f[i][j - 1], f[i + 2 ^ (j - 1)][j - 1]表示,即f[i][j] = max(f[i][j - 1], f[i + 2 ^ (j - 1)][j - 1],
(4)对于给定的询问l, r,定义k 为满足 2 ^ k <= r - l + 1的最大k,由此max(a[l…r])=max(f[l, k], f[r - 2 ^ k + 1 ,k])。样例如下图:
Python
import sys
from math import floor, log
input = lambda:sys.stdin.readline().rstrip()
n = int(input())
a = [0] + list(map(int, input().split()))
f = [[0 for i in range(18)] for i in range(n + 10)]
for j in range(18):
i = 1
while i + 2 ** j - 1 <= n:
if not j:f[i][j] = a[i]
else: f[i][j] = max(f[i][j - 1], f[i + 2 ** (j - 1)][j - 1])
i += 1
for _ in range(int(input())):
l, r = map(int, input().split())
k = floor(log(r - l + 1, 2))
print(max(f[l][k], f[r - (1 << k) + 1][k]))