题目描述

农夫 John 有一群牛按同一序列排队。他想让一些连续排队的牛参加飞盘比赛，但希望参赛牛的身高差别不要太大。现在给出了牛的身高和一些可能的牛的选择，请计算每组参赛牛中最高和最矮的牛的身高差。

样例

输入：
6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出：
6
3
0

算法思路

1. 首先，我们需要建立一个数据结构来快速获取任意连续区间的最大值和最小值。这里可以使用线段树或者ST表来实现。ST表是一种基于动态规划的方法，能够在 $O(1)$ 的时间内查询任意区间的最值。

2. 其次，对于每个查询，我们使用ST表来计算给定区间内的最大值和最小值，然后计算它们的差值即可得到答案。

算法实现

初始化

import math

N = 50010  # 定义常量N
M = 16  # 定义常量M

# 输入n和Q
n, Q = map(int, input().split())
h = [0]*(n+10)  # 初始化数组h

# 输入n个数到数组h中
for i in range(n):
    h[i] = int(input())

# 构建log数组，log[i]表示log2(i)的整数部分
log = [0] * (N + 1)
for i in range(1, n + 1):
    log[i] = int(math.log(i, 2))

# 构建ST表
f = [[0] * (M+10) for _ in range(N)]  # f[i][j]表示从i开始，长度为2^j的区间的最大值
g = [[0] * (M+10) for _ in range(N)]  # g[i][j]表示从i开始，长度为2^j的区间的最小值

# 初始化f和g数组
for i in range(1, n + 1):
    f[i][0] = g[i][0] = h[i - 1]

# 填充f和g数组
for j in range(1, M):
    for i in range(1, n + 1):
        if i + (1 << j) - 1 <= n:
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])
            g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1])

# 处理查询
for _ in range(Q):
    l, r = map(int, input().split())
    t = log[r - l + 1]  # 根据查询区间长度计算所需的log值
    maxh = max(f[l][t], f[r - (1 << t) + 1][t])  # 区间最大值
    minh = min(g[l][t], g[r - (1 << t) + 1][t])  # 区间最小值

    print(maxh - minh)  # 输出区间最大值和最小值的差值

时间复杂度分析

构建ST表的时间复杂度为 $O(n \log n)$，处理每个查询的时间复杂度为 $O(1)$，因此总体时间复杂度为 $O((n + Q) \log n)$。