[USACO07JAN] Balanced Lineup G

GitHub跳转原题关系图返回列表

分别建立区间最小值和最大值 ST 表，让每次静态区间极差查询 O(1) 完成。

OJ: luogu

题目 ID: P2880

难度:普及/提高-

标签:ST表区间最值python

日期: 2026-01-17 20:25

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

静态数组上回答大量区间最高值减最低值。

思路

ST 表第 level 层保存长度 2level2^{level} 区间的最小值或最大值。查询 [l,r] 时取 level=floor(log2(length))，用左右两个允许重叠的长度 2level2^{level} 区间覆盖查询范围；min/max 满足幂等性，重叠不会影响答案。

Python 知识

  • array("i") 紧凑保存各层数据，两个 ST 表总共只需 O(nlog⁡n)O(n\log n) 个 32 位整数。
  • 生成器直接构造下一层数组，不创建额外列表。
  • 预处理 logs[length] 后，每次询问只做常数次下标访问。

代码

python
import sys
from array import array


data = iter(map(int, sys.stdin.buffer.read().split()))
n, queries = next(data), next(data)
heights = array("i", (next(data) for _ in range(n)))
logs = [0] * (n + 1)
for i in range(2, n + 1):
    logs[i] = logs[i // 2] + 1

minimum = [heights]
maximum = [heights]
level = 1
while 1 << level <= n:
    half = 1 << (level - 1)
    length = n - (1 << level) + 1
    previous_min, previous_max = minimum[-1], maximum[-1]
    minimum.append(array("i", (min(previous_min[i], previous_min[i + half])
                               for i in range(length))))
    maximum.append(array("i", (max(previous_max[i], previous_max[i + half])
                               for i in range(length))))
    level += 1

answers = []
for _ in range(queries):
    left, right = next(data) - 1, next(data) - 1
    level = logs[right - left + 1]
    start = right - (1 << level) + 1
    high = max(maximum[level][left], maximum[level][start])
    low = min(minimum[level][left], minimum[level][start])
    answers.append(str(high - low))
print("\n".join(answers))

复杂度

预处理 O(nlog⁡n)O(n\log n)，每次查询 O(1)O(1)，空间 O(nlog⁡n)O(n\log n)。

总结

静态、可重叠的区间最值查询是 ST 表的标准使用场景。