ST 기반 RMQ 구현

1.RMQ：Range Minimum/Maximum Query。구간 최 값 문의.배열 에 기반 한 작업 입 니 다. 예 를 들 어 배열 a 에 대해 구간 (l, r) 에서 a 의 최대 치 를 물 어 보 는 것 입 니 다.
2. RMQ 문 제 는 직접적인 폭력, 선분 수 / 트 리 배열, ST 등 여러 가지 해결 방법 이 있 습 니 다. 이 안에 ST (sparse table: 점프 표 라 고도 함) 가 있 습 니 다. 구간 을 수정 하지 않 을 때 좋 은 해결 방법 입 니 다. 평균 시간 복잡 도 는 O (nlogn) 이 고 가 벼 우 며 선분 수 와 같은 데이터 구조 에 필요 한 공간 이 적 습 니 다.
3. ST 의 기본 사상: ST 의 기 초 는 질문 의 답 이 이러한 특징 을 가지 고 있다 는 것 이다. 구간 가산 성 이다. 즉, 한 문제 에 대해 우리 가 문제 의 구간 을 2 분 으로 나 누 면 우 리 는 왼쪽 구간 의 답 을 구 할 수 있 고 오른쪽 구간 의 답 을 구 할 수 있 으 며 두 사람 을 결합 하면 문제 의 답 을 구 할 수 있다. 이런 문제 가 적합 하 다. 예 를 들 어 최대 최소 치 / 구간 gcd 등 이다.우 리 는 구간 의 최대 값 으로 ST 를 배 웁 니 다. 우 리 는 전체 구간 의 최대 값 이 좌우 구간 의 가장 큰 값 과 같다 는 것 을 알 고 있 습 니 다. 그러면 우 리 는 구간 을 2 분 으로 나 눌 수 있 습 니 다. 왼쪽 에서 가장 큰 값 을 구하 고 오른쪽 에서 하 나 를 구하 고 가장 큰 값 을 구 할 수 있 습 니 다. 이렇게 보면 매우 간단 합 니 다. ST 의 사고방식 은 기본적으로 이것 입 니 다. ST 에서 우 리 는 DP 배열 이 있 습 니 다. 이 DP 의 의 미 는 DP [m] 입 니 다.[n], m 를 기점 으로 길 이 는 pow (2, n) 구간 의 최대 치 입 니 다.

ll dp[maxn][20];
ll f[maxn];

void ST()
{
	int i, j, k;
	for (i = 1; i <= maxn; i++)
		dp[i][0] = f[i];
	k = log((double)(maxn + 1)) / log(2.0);
	for (j = 1; j <= k; j++)
		for (i = 1; i + (1 << j) - 1 <= maxn; i++)
			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq_max(int l, int r)
{
	if (l>r)
		return 0;
	int k = log((double)(r - l + 1)) / log(2.0);
	return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

4. POJ 3368. 이것 은 ST 를 이용 하여 RMQ 문 제 를 해결 하 는 누 드 문제 입 니 다. 우 리 는 스스로 예비 처 리 된 정 보 를 추가 해 야 합 니 다. 이 문 제 는 구간 을 주 고 이 구간 에서 가장 많이 발생 하 는 그 수 를 찾 는 것 입 니 다. 주의 하 세 요. 여기 에는 매우 중요 한 정보 가 있 습 니 다. 이 데 이 터 는 단조 로 운 것 입 니 다. 즉, 같은 데이터 가 한 덩어리 에 있다 는 것 입 니 다. 공간 국 이 있 습 니 다.부 성. 우 리 는 ST 를 어떻게 이용 합 니까? 우 리 는 먼저 하나의 배열 f 로 입력 한 정 보 를 미리 처리 합 니 다. f [i] 는 배열 부터 a [0] 까지 현재 이 위치 에서 a [i] 와 같은 데이터 의 갯 수 를 표시 합 니 다. 우 리 는 이 데이터 들 이 모두 i 의 첨부 파일 에 있 을 것 이라는 것 을 알 고 있 습 니 다. 반지름 의 모양 이 있 습 니 다. 그러면 우 리 는 ST 를 사용 할 수 있 습 니 다. 그리고 우 리 는 구간 의 문 제 를 고려 하여 구간 [l, r] 에 대해 서 입 니 다.우 리 는 ST 를 사용 하여 f 배열 이 이 구간 에서 가장 높 은 값 을 구하 고 있 습 니 다. 꼭 우리 가 원 하 는 것 은 아 닙 니 다. 왼쪽 구간 의 문제 로 인해 l 왼쪽 의 정 보 를 모 르 면 우 리 는 어떻게 해 야 합 니까?.........................................................................................

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
ll a[maxn];
ll dp[maxn][20];
ll f[maxn];

void ST()
{
	int i, j, k;
	for (i = 1; i <= maxn; i++)
		dp[i][0] = f[i];
	k = log((double)(maxn + 1)) / log(2.0);
	for (j = 1; j <= k; j++)
		for (i = 1; i + (1 << j) - 1 <= maxn; i++)
			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq_max(int l, int r)
{
	if (l>r)
		return 0;
	int k = log((double)(r - l + 1)) / log(2.0);
	return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
#pragma warning(disable:4996)
int main()
{
	int n, q;
	while (~scanf("%d", &n)&&n)
	{
		scanf("%d", &q);
		for (int i =1; i <=n; i++)
		{
			scanf("%d", &a[i]);
			if (i == 1)
			{
				f[i] = 1;
				continue;
			}
			if (a[i]==a[i-1])
			{
				f[i] = f[i - 1] + 1;
			}
			else
			{
				f[i] = 1;
			}
		}
		ST();
		int l;
		int r;
		for (int i = 0; i < q; i++)
		{
			scanf("%d%d", &l, &r);
			int t = l;
			while (a[t] == a[t - 1] && t <= r)
				t++;
			int cnt = rmq_max(t, r);
			int ans = max(t - l, cnt);
			printf("%d
", ans);
		}
	}
    return 0;
}

후기: sorry, 이전 코드 CE, 어색... POJ 아직 만능 머리 못 써..................................................................