Poj 3368 RMQ 방법. - 사실 dp의 변형에 불과합니다.

전편에서는 세그먼트 트리 만들기, 이거 하나는 RMQ 방법으로 만든 거고 RMQ 배우기도 하고.
RMQ라고 하기엔 사실상 dp의 변형이다.
RMQ 정의:
RMQ(Range Minimum/Maximum Query) 질문은 길이가 n인 수열 A에 대해 RMQ(A, i, j)(i, j<=n)를 약간 묻고 수열 A에 i, j에 표시된 최소(대) 값을 되돌려주는 것이다. 즉, RMQ 질문은 구간 최소값을 구하는 문제를 가리킨다.
주요 방법 및 복잡성은 다음과 같습니다.
1. 수수함(즉 검색), O(n)-O(qn) 온라인.
2. 세그먼트 트리, O(n)-O(qlogn) 온라인.
3. ST(실질적으로 동적 기획), O(nlogn)-O(1)online.
ST 알고리즘(Sparse Table)은 최대치를 구하기 위해 d[i, j]를 설정하면 [i, i+2^j-1]이라는 구간 내의 최대치를 나타낸다. 그러면 [a, b] 구간의 최대치를 물었을 때 답은 max(d[a, k], d[b-2^k+1, k])이다. 그 중에서 k는 2^k<=b-a+1(즉 길이)를 만족시키는 가장 큰 k, 즉 k=[ln(b-a+1)/ln(2)]이다.
d의 구법은 동적 기획, d[i, j]=max(d[i, j-1], d[i+2^(j-1), j-1])로 할 수 있다.
4. RMQ 표준 알고리즘: 먼저 LCA(Lowest Common Ancestor)로 규정한 다음에 제약 RMQ, O(n)-O(1)online으로 규정한다.
먼저 원래 수열에 따라 데카르트 트리를 만들어 문제의 온라인 시간 내에 LCA 문제로 규정한다.LCA 문제는 온라인 시간 내에 RMQ를 구속하는 것으로 규정할 수 있다. 즉, 수열에서 임의의 두 개의 인접한 수의 차는 모두 +1 또는 -1의 RMQ 문제이다.RMQ를 구속하는 데는 O(n)-O(1)의 온라인 해법이 있기 때문에 전체 알고리즘의 시간 복잡도는 O(n)-O(1)이다.
 
이곳의 상태 방정식 dp[j][i]=max(dp[j][i-1], dp[j+(1<(i-1)][i-1])];
dp[j][i]는 j부터 시작하기 전 2^i 개수 중 최대 중복 횟수를 표시합니다.
이것들이 있어서, 다른 것은 전편과 기본적으로 같기 때문에 코드가 매우 비슷하다.
 

//RMQ
#include <iostream>
#include <cmath>
using namespace std;

int arr[100010],hash[100010];

struct Part
{
	int s, e, cnt;
}part[100010];
int dp[100010][18];//dp[i][j] is for : the max value rang from i to (i + 2^j - 1)

int Max(int a, int b)
{
	return a >  b ? a : b;
}
void Dp(int n)
{
	int i, j, tmp;
	for (i = 1; i <= n; ++ i)
	{
		dp[i][0] = part[i].cnt;
	}
	tmp = log(n + 1.0)/log(2.0);
	for (i = 1; i <= tmp; ++ i)
	{
		for (j = 1; j + (1 << i) - 1 <= n ; ++ j)
		{
			dp[j][i] = Max(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
		}
	}
}
int getMax(int a, int b)
{
	int k = (int )((log(b - a + 1.0)) / log(2.0));
	return Max(dp[a][k], dp[b - (1 << k) + 1][k]);
}
int main()
{
	int n, q;
	while (scanf("%d", & n) && n)
	{
		scanf("%d", & q);
		for (int i = 1; i <= n; ++ i)
		{
			scanf("%d", & arr[i]);
		}
		memset(part, 0, sizeof(part));
		int id = 1;
		part[1].s = id;
		for (int i = 1; i <= n; ++ i)
		{
			part[id].cnt ++;
			hash[i] = id;
			if (arr[i] != arr[i + 1] || i == n)
			{
				part[id].e = i;
				++ id;
				part[id].s = i + 1;
			}
		}
		Dp(id - 1);
		int a, b;
		while (q --)
		{
			scanf("%d %d", & a, & b);
			if (hash[a] == hash[b])//the same part
			{
				printf("%d
", b - a + 1);
			}
			else// two situations
			{
				int n1 = part[hash[a]].e - a + 1;
				int n2 = b - part[hash[b]].s + 1;
				int n3 = 0;
				if (hash[b] - hash[a] > 1)
				{
					n3 = getMax(hash[a] + 1, hash[b] -  1);
				}

				printf("%d
", Max(Max(n1, n2),n3));
			}
		}
	}
	return 0;
}