【题目来源】
洛谷：[P2880 USACO07JAN] Balanced Lineup G - 洛谷
【题目描述】
每天，农夫 John 的 \(n\ (1\le n\le 5\times 10^4)\) 头牛总是按同一序列排队。
有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 \(q\ (1\le q\le 1.8\times10^5)\) 个可能的牛的选择和所有牛的身高 \(h_i\ (1\le h_i\le 10^6,1\le i\le n)\)。他想知道每一组里面最高和最低的牛的身高差。
【输入】
第一行两个数 \(n,q\)。
接下来 \(n\) 行，每行一个数 \(h_i\)。
再接下来 \(q\) 行，每行两个整数 \(a\) 和 \(b\)，表示询问第 \(a\) 头牛到第 \(b\) 头牛里的最高和最低的牛的身高差。
【输出】
输出共 \(q\) 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。
【输入样例】
6 3
1
7
3
4
2
5
1 5
4 6
2 2
【输出样例】
6
3
0
【算法标签】
《洛谷 P2880 Balanced Lineup》 #线段树# #树状数组# #ST表# #USACO# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义常量
const int N = 50005; // 最大数据量// 定义数组
int a[N][20]; // ST表，用于存储区间最大值，a[i][j]表示从i开始长度为2^j的区间最大值
int b[N][20]; // ST表，用于存储区间最小值，b[i][j]表示从i开始长度为2^j的区间最小值
int n; // 数据个数
int q; // 查询次数
int maxn; // 临时变量，存储区间最大值
int minn; // 临时变量，存储区间最小值int main()
{// 读入数据个数和查询次数cin >> n >> q;// 读入初始数据并初始化ST表的第一层for (int i = 1; i <= n; i++){cin >> a[i][0]; // 输入第i个数b[i][0] = a[i][0]; // 同时赋值给最小值表}// 构建ST表for (int j = 1; j <= 20; j++) // j表示区间长度为2^j{for (int i = 1; i + (1 << j) - 1 <= n; i++) // 确保区间不越界{// 计算区间[i, i+2^j-1]的最大值// 拆分为两个区间：[i, i+2^(j-1)-1] 和 [i+2^(j-1), i+2^j-1]a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);// 计算区间[i, i+2^j-1]的最小值b[i][j] = min(b[i][j - 1], b[i + (1 << (j-1))][j - 1]);}}// 处理查询while (q--){int l, r; // 查询区间[l, r]cin >> l >> r;// 计算区间长度的对数向下取整int k = log2(r - l + 1);// 查询区间最大值// 将区间[l, r]拆分为两个有重叠的区间：// [l, l+2^k-1] 和 [r-2^k+1, r]maxn = max(a[l][k], a[r - (1 << k) + 1][k]);// 查询区间最小值minn = min(b[l][k], b[r - (1 << k) + 1][k]);// 输出区间极差（最大值减最小值）cout << maxn - minn << endl;}return 0;
}
【运行结果】
6 3
1
7
3
4
2
5
1 5
6
4 6
3
2 2
0