洛谷 Balanced Lineup G P2880 模版

原题/problem/P2880

题目描述

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 180,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

每天,农夫 John 的n(1≤n≤5×10^4) 头牛总是按同一序列排队。

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

输入格式

Line 1: Two space-separated integers, N and Q.

Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i

Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

第一行两个数n,q。

接下来 ????n 行，每行一个数 hi。

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

输出格式

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

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

输入输出样例

输入 #1

输出 #1

6
3
0

解题思路

ST算法。

原理：一个大区间如果可以被两个小区间覆盖，那么大区间的最值等于两个小区间的最值。

我们先说说暴力吧，很简单，每次查询，逐一比较，就可以得到答案，如果查询m次，比较n次，那么时间复杂度为O(mn)。超时。

那么有没有办法让时间缩短，ST来了，其实也是基于倍增原理（不了解可以看国旗计划），把一个大区间分成1,2^1,2^2,……2^k元素数量的小区间（注意，区间可以重合），接下来可以利用动态规划把每一个小区间的结果记录下来也就是dp[s][0]，那么就可以得出递推关系(最小值举例):

dp[s][k]=min{dp[s][k-1]+dp[s+(1<<(k-1)][k-1]}

这样下来也就得到了所有[l,r]的最小值了，最大值相同，改为max就可以了。

那么我们如何找区间位置呢,找到这两个小区间呢，这也有递推公式(最小值举例)：

min(d[l][k],d[r-(1<<k)+1][k])

本人菜鸡，解释的不是很清楚。

对了，k的求法忘记说了，可以直接用log2(n),或者自己用数组模拟（快一点），具体代码不是很难。

时间复杂度（nlogn)

AC代码

#include <iostream>
using namespace std;
#include <algorithm>
const int N=5e4+5;
int n,q,l,r;
int dp_min[N][20],dp_max[N][20],a[N],LOG2[N];

void init(){
	LOG2[0]=-1;
	for(int i=1;i<=n;i++)	LOG2[i]=LOG2[i>>1]+1; 
	for(int i=1;i<=n;i++){
		dp_max[i][0]=a[i];
		dp_min[i][0]=a[i];
	}
	
	int p=LOG2[n];
	for(int k=1;k<=p;k++){
		for(int s=1;s+(1<<k)<=n+1;s++){//s本身算一位，所以要<=n+1 ,不然最后一组存储不到 
			dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);//s+(1<<(k-1)刚好位移到2^(k-1)+1 
			dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
		}
	}
}
void st_query(int l,int r){
	int k=LOG2[r-l+1];
	int x=max(dp_max[l][k],dp_max[r-(1<<k)+1][k]); 
	int y=min(dp_min[l][k],dp_min[r-(1<<k)+1][k]);
	printf("%d\n",x-y);
}
int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	init();
	for(int i=1;i<=q;i++) {
		scanf("%d %d",&l,&r);
		st_query(l,r);
	}
	
	return 0;
}

秒客网