POJ 3368 Frequent values (RMQ)

제목 유형  RMQ
제목
최대 100000 개의 수 를 포함 하 는 비 체감 수열 을 제시 하 는 데 최대 100000 번 이 있 습 니 다. 매번 L 번 째 숫자 에서 R 번 째 숫자 사이 의 가장 긴 숫자 가 같은 연속 서브 시퀀스 가 얼마나 되 는 지 물 어 봅 니 다.
문제 풀이 방법
ST 알고리즘 사용 가능
먼저 원 수열 의 연속 적 인 같은 부분 을 하나의 정수 로 압축 한다. 예 를 들 어 1, 1, 2, 2, 3, 3 을 3, 2, 4 로 압축 하고 압축 후 각 수 에 대응 하 는 원자 서열 의 시작 위 치 를 기록한다.
그리고 하나의 배열 dp [i] [j] 를 미리 처리 하 는 것 은 i 번 째 위치 부터 (1 < j) 개 수 를 나타 내 는 범위 내 최대 치 입 니 다.
그러면 질문 L - > R 에 대해 먼저 L 이라는 위 치 를 구하 고 앞으로 얼마나 똑 같은 지 를 구 한 다음 에 R 이라는 위치 에서 앞으로 몇 개의 똑 같은 기록 이 있 는 지 그들의 최대 치 는 중간 에 똑 같은 구간 에 대응 하 는 수 와 비교 하여 구체 적 으로 코드 를 봅 니 다.
참조 코드 - 궁금 한 점 이 있 으 시 면 아래 에 댓 글 을 남 겨 주시 면 바로 답 해 드 리 겠 습 니 다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 10;
const int INF = 1<<29;
const double e = 2.71828;

int a[maxn], b[maxn], num[maxn], sta[maxn];
int dp[maxn][20];

int main() {
  //freopen("in", "r", stdin);
	int n, q;
	while(scanf("%d%d", &n, &q) == 2) {
		memset(dp, 0, sizeof(dp));
		for( int i=0; i<n; i++ ) {
			scanf("%d", &a[i]);
		}
		int pre = a[0], cut = 1;
		int tn = 0; //tn              
		sta[0] = 0; //                   
		for( int i=1; i<n; i++ ) {
			if(a[i] == pre) cut++;
			else {
				b[tn] = a[i-1]; //ｂ                   
				num[tn++] = cut;
				sta[tn] = i;
				cut = 1;
				pre = a[i];
			}
		}
		b[tn] = a[n-1]; num[tn++] = cut;
		for( int i=0; i<tn; i++ ) dp[i][0] = num[i]; //   dp  

		for( int j=1; (1<<j)<tn; j++ ) {
			for( int i=0; i<tn && i+(1<<j)-1<tn; i++ ) {
				dp[i][j] = max(dp[i][j-1], dp[i+(1<<j)-1-(1<<(j-1))+1][j-1]);
			}
		}
		for( int i=0; i<q; i++ ) {
			int l, r;
			scanf("%d%d", &l, &r);
			l--, r--;
			int L = lower_bound(b, b + tn, a[l]) - b;
			int R = lower_bound(b, b + tn, a[r]) - b;
			int ans = 0;
			if(L == R) ans = max(ans, r-l+1);
			else {
				ans = max(ans, sta[L+1] - l); //  L    L R       
				ans = max(ans, r - sta[R] + 1); // R    L Ｒ       
				if(L+1 != R) {
					double tk = log(1.0*R-1-(L+1)+1)/log(2.0);
					int tmp = tk;
					ans = max(ans, max(dp[L+1][tmp], dp[R-1-(1<<tmp)+1][tmp]));
				}
			}
			printf("%d
", ans);
		}
	}
	return 0;
}