题目描写叙述
农夫约翰的 N (1 ≤ N ≤ 50,000) 头奶牛，每天挤奶时总会按相同的顺序站好。
一日。农夫约翰决定为奶牛们举行一个“终极飞盘”比赛。为简化问题。他将从奶牛队列中选出一个连续区间来进行游戏。
只是，參加游戏的奶牛要玩的开心的话就不能在身高上差距太大。
农夫约翰制定了 Q (1 ≤ Q ≤ 200,000) 个预定的參赛组，给出它们的身高 (1 ≤ 身高 ≤ 1,000,000)。对每一个參赛组。他须要你帮助确定组中最高牛和最低牛的身高差。
输入格式
- 第 1 行: 两个空格隔开的整数，N 和 Q。
- 第 2..N+1 行: 第 i+1 行包括一个整数表示第 i 头牛的身高。
- 第 N+2..N+Q+1 行: 两个整数 A 和 B(1 ≤ A ≤ B ≤ N)，表示一个从 A 到 B 的參赛组区间。
输出格式
- 第 1..Q 行: 每行包括一个整数来表示区间上最大身高差。
例子输入
6 3
1
7
3
4
2
5
1 5
4 6
2 2
例子输出
6
3
0
题解：st表练习题。 。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a,b,q,ffmin[60000][30],ffmax[60000][30];
int in()
{
int x=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
freopen("lineup.in","r",stdin);
freopen("lineup.out","w",stdout);
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)
{
a=in();
ffmin[i][0]=a;ffmax[i][0]=a;
}
for (int j=1;j<=20;j++)
for (int i=1;i<=n;i++)
if (i+(1<<j)-1<=n)
{
ffmin[i][j]=min(ffmin[i][j-1],ffmin[i+(1<<(j-1))][j-1]);
ffmax[i][j]=max(ffmax[i][j-1],ffmax[i+(1<<(j-1))][j-1]);
}
else break;
for (int i=1;i<=q;i++)
{
int k,maxx,minn;
a=in();b=in();
k=(int)(log(b-a+1.0)/log(2.0));
maxx=max(ffmax[a][k],ffmax[b-(1<<k)+1][k]);
minn=min(ffmin[a][k],ffmin[b-(1<<k)+1][k]);
printf("%d\n",maxx-minn);
}
}