【RMQ】poj 3264 Balanced Lineup

먼저 사전 프로세싱을 단일 DP로 처리합니다.a는 구간 최값을 요구하는 수열로 f[i,j]는 i개수부터 연속 2^j개수 중 최대값을 나타낸다.예를 들어 수열 3, 2, 4, 5, 6, 81, 297, f[1,0]는 첫 번째 수부터 길이가 2^0=1의 최대치인데 사실은 3이라는 수이다.f[1,2]=5, f[1,3]=8, f[2,0]=2, f[2,1]=4...여기서 f[i,0]는 사실 a[i]와 같다는 것을 알 수 있다.이렇게 해서 DP의 상태, 초기값이 모두 있고 나머지는 상태 이동 방정식이다.우리는 f[i, j](j≥1)를 평균 두 단락(j≥1일 때 f[i, j]는 짝수 숫자가 틀림없기 때문)으로 나누고 i부터 i+2^(j-1)-1은 한 단락, i+2^(j-1)부터 i+2^j-1까지는 한 단락(길이는 모두 2^(j-1))이다.상례로 설명하자면 i=1, j=3일 때 3, 2, 4, 5와 6, 8, 1, 2 두 단락이다.f가 바로 이 두 단락의 최대치 중의 최대치다.그래서 우리는 동규방정식 F[i, j]=max(F[i, j-1], F[i+2^(j-1), j-1])를 얻었다.
다음은 가장 높은 값을 얻는 것이다. f를 계산하는 것이 무슨 소용이 있는지 생각지도 못할 것이다. 일반적으로 max를 계산하려면 O(logn), 심지어 O(n)까지 계산해야 한다.하지만 좋은 방법이 하나 있다. O(1)까지 해냈다.아니면 헤어져?예를 들어 상례에서 우리가 구간[2,8]의 최대치를 요구하면 이를 [2,5]와 [5,8] 두 구간으로 나누어야 한다. 왜냐하면 이 두 구간의 최대치는 f[2,2]와 f[5,2]로 직접 얻을 수 있기 때문이다.일반적인 상황으로 확장하면 구간 [l,r]을 두 개의 길이가 2^n인 구간으로 나누는 것이다(f가 대응할 것을 보장한다).표현식을 직접 지정하려면 다음과 같이 하십시오.
k:=trunc(ln(r-l+1)/ln(2));
ans:=max(F[l,k],F[r-2^k+1,k]);
이렇게 해서 l부터 길이가 2^k인 구간과 r-2^k+1부터 길이가 2^k인 구간의 최대치를 계산했다(표현식이 비교적 번거롭고 세부적인 문제는 1을 더하고 1을 줄이는 것과 같이 자세히 고려해야 한다). 양자 중 비교적 큰 것이 전체 구간 [l, r]의 최대치이다.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;

int height[50005];
int n, q;
int mx[50005][16], mn[50005][16];

// Initialize arrays
void rmq_init(){
	for(int i=0; i<n; i++){
		mx[i][0] = i;
		mn[i][0] = i;
	}
	
	for(int i=1; (1<<i)<=n; i++){
		for(int j=0; (j+(1<<i)-1)<n; j++){
			// Update minimal records
			if(height[mn[j][i-1]] < height[mn[j+(1<<(i-1))][i-1]])
				mn[j][i] = mn[j][i-1];
			else 
				mn[j][i] = mn[j+(1<<(i-1))][i-1];
			// Update maximal records
			if(height[mx[j][i-1]] > height[mx[j+(1<<(i-1))][i-1]])
				mx[j][i] = mx[j][i-1];
			else
				mx[j][i] = mx[j+(1<<(i-1))][i-1];
		}
	}
	return;
}

// Response q query
int query(int left, int right){
	int k = 0;
	int length = right-left+1;
	while((1<<(k+1)) < length)
		k++;	
	int mini = min(height[mn[left][k]], height[mn[right-(1<<k)+1][k]]);
	int maxi = max(height[mx[left][k]], height[mx[right-(1<<k)+1][k]]);
	//cout<<"maxi: "<<maxi<<" mini: "<<mini<<endl;
	return maxi-mini;
}

int main(){	
	scanf("%d%d", &n,&q);
	for(int i=0; i<n; i++)
		scanf("%d", height+i);
	rmq_init();
	for(int i=0; i<q; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d
", query(l-1, r-1));
	}
	//system("pause");
	return 0;
}