poj 3368 RMQ 线段树 离散化

一 题意：给定递增序列，找出连续出现的最长子序列，然后求出它的长度，即最高频率。注意必须是连续出现。

 

二 算法：可以事先求出序列中每个数字的最高频率，比如序列(-1,-1,1,1,1,1,3,10,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\n", ans);
		}
	}

	return 0;
}