欢迎大家订阅我的专栏算法题解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#【代码详解】#includebits/stdc.husingnamespacestd;// 定义常量constintN50005;// 最大数据量// 定义数组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(){// 读入数据个数和查询次数cinnq;// 读入初始数据并初始化ST表的第一层for(inti1;in;i){cina[i][0];// 输入第i个数b[i][0]a[i][0];// 同时赋值给最小值表}// 构建ST表for(intj1;j20;j)// j表示区间长度为2^j{for(inti1;i(1j)-1n;i)// 确保区间不越界{// 计算区间[i, i2^j-1]的最大值// 拆分为两个区间[i, i2^(j-1)-1] 和 [i2^(j-1), i2^j-1]a[i][j]max(a[i][j-1],a[i(1(j-1))][j-1]);// 计算区间[i, i2^j-1]的最小值b[i][j]min(b[i][j-1],b[i(1(j-1))][j-1]);}}// 处理查询while(q--){intl,r;// 查询区间[l, r]cinlr;// 计算区间长度的对数向下取整intklog2(r-l1);// 查询区间最大值// 将区间[l, r]拆分为两个有重叠的区间// [l, l2^k-1] 和 [r-2^k1, r]maxnmax(a[l][k],a[r-(1k)1][k]);// 查询区间最小值minnmin(b[l][k],b[r-(1k)1][k]);// 输出区间极差最大值减最小值coutmaxn-minnendl;}return0;}【运行结果】6 3 1 7 3 4 2 5 1 5 6 4 6 3 2 2 0