poj 3368 RMQ 선분 수 이산 화

한 문제 의 뜻: 증가 서열 을 정 하고 연속 적 으로 나타 나 는 최 장 자 서열 을 찾 은 다음 에 그 길이, 즉 최고 주파 수 를 구한다.주 의 는 반드시 연속 적 으로 나타 나 야 한다.
 
이 알고리즘: 서열 중의 모든 숫자의 최고 주파 수 를 미리 구 할 수 있다. 예 를 들 어 서열 (- 1, - 1, 1, 1, 1, 1, 1, 3, 10, 10) 에서 각 숫자의 최고 주파 수 는 다음 과 같다.
(- 1: 2), (1: 4), (3: 1), (10, 3) 구간 [s, t] 에 대해 서 는 첫 부분 과 끝 부분 만 같은 숫자 에서 절 단 될 수 있 으 며, 머리 끝의 중간 부분 숫자 를 제거 할 수 있 습 니 다.
최고 주파 수 는 직접 얻 을 수 있다.마지막 으로 첫 번 째 부분, 꼬리 부분 과 중간 부분의 빈 도 를 비교 하면 [s, t] 의 최고 빈 도 를 얻 을 수 있 고 세 가지 상황 으로 나 누 어 토론 할 수 있다.
유색 부분 은 찾 으 려 는 구간 [s, t] 이 고 빨간색 은 첫 번 째 부분 을 대표 하 며 파란색 은 꼬리 부분 을 대표 하고 녹색 은 중간 부분 을 대표 합 니 다.
1） 1111111111111
한 가지 숫자 만 있 으 면 바로 되 돌려 줍 니 다 (t - s + 1)
2） 1111122222222222
첫 부분 과 끝 부분 을 제거 한 후 중간 부분 이 없 으 면 첫 번 째 주파수 와 꼬리 주파수 의 최대 치 를 되 돌려 줍 니 다.
3） 111111222333444444
첫 부분 과 끝 부분 을 제거 한 후 중간 부분 은 222333 이 며, 온라인 세그먼트 트 리 에서 2 와 3 의 최고 주파 수 를 찾 아 첫 부분 꼬리 주파 수 를 종합해 답 을 얻 었 다.
 
    문 제 는 중간 부분의 최고 주파 수 를 찾 는 것 이다. 중간 부분 에 N 개의 서로 다른 숫자 가 있 는데 만약 에 모든 숫자 를 한 번 스 캔 하면 알고리즘 이 복잡 하 다.
O (N) 를 위해 반드시 시간 을 초과 하고 처리 할 때 먼저 서열 을 분리 한다. 즉, 연속 적 으로 나타 난 숫자 를 한 점 에 모 으 고 그 빈 도 를 계산 하면 원래 의 서열 이 바뀐다.
일련의 점 집합 으로 바 뀌 었 다. 원래 시리즈 에 비해 이 점 집합 은 훨씬 작 았 다. 그리고 이 점 집합 에 따라 선분 트 리 를 만 들 고 선분 은 점 구간 내의 최고 주파 수 를 저장 했다.
선분 트 리 에서 찾 으 면 알고리즘 복잡 도가 O (logN) 로 변 합 니 다.
 
코드
 

#include <stdio.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define MAX(a, b) (a) > (b) ? (a) : (b)
#define inf 20000000
#define N 100001

int tree[262144];	/*             */
int pos[N];			/* pos[i] = j   i         j */

/*   [l,r]     ，  num */
struct node {
	int l, r;
	int num;
}; 
struct node table[N];

int M;

void build_tree(int n)
{
	int 	i;

	for (M = 1; M < (n+2); M <<= 1);
	//         
	for (i = 1; i <= n; i++) {
		tree[i+M] = (table[i].r-table[i].l+1);
	}
	//       
	for (i = n+1; i%M != 1; i++) {
		tree[(i%M)+M] = -1;
	}
	//    
	for (i = M-1; i > 0 ; i--) {
		tree[i] = MAX(tree[i<<1], tree[(i<<1)+1]);
	}
}

int query(int s, int t)
{
	int 	max_freq;

	max_freq = -1;
	for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
		if (~s&1) {
			max_freq = MAX(max_freq, tree[s^1]);
		}
		if (t&1) {
			max_freq = MAX(max_freq, tree[t^1]);
		}
	}

	return max_freq;
}

int main()
{
	int		n, p, q, i, s, t, ans, ss, tt, num;

	while (scanf("%d %d", &n, &q), n) {
		table[p = 0].num = inf;
		//  ，   
		for (i = 1; i <= n; i++) {
			scanf("%d", &num);
			if (num == table[p].num) {
				table[p].r = i;
				pos[i] = p;
			}
			else {
				p++;
				table[p].l = table[p].r = i;
				table[p].num = num;
				pos[i] = p;
			}
		}

		build_tree(p);

		while (q--) {
			scanf("%d %d", &s, &t);
			//[s,t]      
			if (pos[s] == pos[t]) {
				ans = (t-s+1);
			}
			else {
				ans = -inf;
				/* [s,t]       ，        
				 *            [ss,tt]
				 */
				ss = table[pos[s]].r+1;
				tt = table[pos[t]].l-1;
				if (tt >= ss) {
					ans = query(pos[ss], pos[tt]);
				}
				ans = MAX(ans, MAX(ss-s, t-tt));
			}
			printf("%d
", ans);
		}
	}

	return 0;
}