欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年黄金组真题解析 | 汇总
P2880 Balanced Lineup
【题目来源】
洛谷：[P2880 USACO07JAN] Balanced Lineup G - 洛谷
【题目描述】
每天，农夫 John 的n ( 1 ≤ n ≤ 5 × 10 4 ) n\ (1\le n\le 5\times 10^4)n(1≤n≤5×104)头牛总是按同一序列排队。
有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了q ( 1 ≤ q ≤ 1.8 × 10 5 ) q\ (1\le q\le 1.8\times10^5)q(1≤q≤1.8×105)个可能的牛的选择和所有牛的身高h i ( 1 ≤ h i ≤ 10 6 , 1 ≤ i ≤ n ) h_i\ (1\le h_i\le 10^6,1\le i\le n)hi(1≤hi≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。
【输入】
第一行两个数n , q n,qn,q。
接下来n nn行，每行一个数h i h_ihi。
再接下来q qq行，每行两个整数a aa和b bb，表示询问第a aa头牛到第b bb头牛里的最高和最低的牛的身高差。
【输出】
输出共q qq行，对于每一组询问，输出每一组中最高和最低的牛的身高差。
【输入样例】
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>usingnamespacestd;// 定义常量constintN=50005;// 最大数据量// 定义数组inta[N][20];// ST表，用于存储区间最大值，a[i][j]表示从i开始长度为2^j的区间最大值intb[N][20];// ST表，用于存储区间最小值，b[i][j]表示从i开始长度为2^j的区间最小值intn;// 数据个数intq;// 查询次数intmaxn;// 临时变量，存储区间最大值intminn;// 临时变量，存储区间最小值intmain(){// 读入数据个数和查询次数cin>>n>>q;// 读入初始数据并初始化ST表的第一层for(inti=1;i<=n;i++){cin>>a[i][0];// 输入第i个数b[i][0]=a[i][0];// 同时赋值给最小值表}// 构建ST表for(intj=1;j<=20;j++)// j表示区间长度为2^j{for(inti=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--){intl,r;// 查询区间[l, r]cin>>l>>r;// 计算区间长度的对数向下取整intk=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;}return0;}【运行结果】
6 3 1 7 3 4 2 5 1 5 6 4 6 3 2 2 0
)
