P2880 [USACO07JAN] Balanced Lineup G

题目描述

每天，农夫 John 的 头牛总是按同一序列排队。

有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 个可能的牛的选择和所有牛的身高 。他想知道每一组里面最高和最低的牛的身高差。

输入格式

第一行两个数 。

接下来 行，每行一个数 。

再接下来 行，每行两个整数 和 ，表示询问第 头牛到第 头牛里的最高和最低的牛的身高差。

输出格式

输出共 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。

输入输出样例 #1

输入 #1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出 #1

6
3
0

思路：牛的队列已知且不会改变，求一组里牛的身高的最大差值，其实就是在求最高与最低身高，即静态区间最大最小值查询问题。

我们可以用ST表来解决，同时记录牛从i到i+2^k区间的最大与最小身高，以便于快速查询。

具体代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<unordered_map>
using namespace std;
const int Maxofn=5e4+5;
const int Maxofk=20;
int st_max[Maxofk][Maxofn]={},st_min[Maxofk][Maxofn]={};
int h[Maxofn]={};
int log_table[Maxofn]={};
int n=0,q=0;

int readint(){	//快速读入 
	char ch=getchar();
	int x=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}
void init_log(){	//对log2表进行预处理 
	log_table[1]=0;
	for(int i=2;i<=n;i++){
		log_table[i]=log_table[i/2]+1;
	}
}

int main(){
	n=readint();q=readint();
	for(int i=1;i<=n;i++){	//对表进行初始化 
		h[i]=readint();
		st_max[0][i]=st_min[0][i]=h[i];
	}
	
	init_log();	//对log2表进行预处理 
	
	for(int k=1;k<=Maxofk;k++){	//对最大最小表进行预处理 
		for(int i=1;i+(1<<k)-1<=n;i++){
			st_max[k][i]=max(st_max[k-1][i],st_max[k-1][i+(1<<(k-1))]);
			st_min[k][i]=min(st_min[k-1][i],st_min[k-1][i+(1<<(k-1))]);
		}
	}
	
	while(q--){	//进行查询 
		int a=readint(),b=readint();
		int k=log_table[b-a+1];
		int max_val=max(st_max[k][a],st_max[k][b-(1<<k)+1]);
		int min_val=min(st_min[k][a],st_min[k][b-(1<<k)+1]);
		int ans=max_val-min_val;
		printf("%d\n",ans);
	}
	return 0;
}