`
kenby
  • 浏览: 724741 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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;
}
 

 

 

 

分享到:
评论

相关推荐

    POJ2528-Mayor's posters【区间映射压缩(离散化)+线段树】

    POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========&gt; 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573

    线段树入门学习(二)(兼解POJ3468) JAVA

    在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...

    线段树练习POJ 3264

    线段树的构建通常分为两个阶段:初始化和构造。初始化时,我们将原始数组中的元素逐个放入线段树的叶子节点。构造阶段则是通过一系列的合并操作,自底向上建立线段树的非叶节点。线段树的每个节点保存的信息可能包括...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    线段树入门学习(三)懒操作(兼解POJ1823) JAVA

    // 初始化线段树和懒标签数组 // ... } void update(int l, int r, int val) { // 对[l, r]区间添加val,使用懒惰更新 // ... } int query(int l, int r) { // 查询[l, r]区间的和,传播懒标签 // ... ...

    poj 2352 stars(树状数组,线段树)

    ### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...

    poj2823.cpp.tar.gz_线段树

    在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...

    Frequent Values(poj 3368) C

    在本题目"Frequent Values (poj 3368)"中,我们需要解决的是一个与数据处理和算法相关的编程问题。该题目是广东工业大学《算法和高级数据结构教程课程设计》的一部分,采用C语言进行实现。下面我们将深入探讨这个...

    线段树题目

    - **POJ 1151**:结合了线段树和离散化的技巧来求解矩形面积的并集。这需要对输入的坐标进行离散化处理,以减少空间复杂度,并使用线段树维护区间信息。 - **POJ 1177**:求解矩形周长的并集。此题与POJ 1151类似,...

    poj 2763 housewife Wind

    poj 2763 程序 线段树 LCA 2000MS AC

    ACMer需要掌握的算法讲解 (2).docx

    * RMQ:POJ3264、POJ3368 * 并查集的高级应用:POJ1703、POJ2492 * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ...

    POJ 部分题解 解题报告

    10. **POJ 2528 线段树.txt**:这是第三个线段树相关的题目,解题报告可能会深入讲解线段树在不同场景下的应用。 通过阅读这些解题报告,你可以学习到各种高级算法的应用,如动态规划、搜索算法、数据结构(如线段...

    poj题目分类

    * RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 poj1703、poj2492。 * KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 *...

    二维树状数组学习之二:练习POJ 1195

    在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...

    poj训练计划.doc

    - RMQ(区间查询):如`poj3264, poj3368`。 - 并查集的高级应用:如`poj1703, poj2492`。 - **搜索** - 最优化剪枝和可行性剪枝:如`poj3411, poj1724`。 - **动态规划** - 复杂的动态规划:如`poj1191, poj...

    ACM数据结构之树状数组和线段树

    ### ACM数据结构之树状数组和线段树 #### 线段树 线段树是一种非常有效的数据结构,主要用于解决区间查询问题。它能够快速地处理区间内的各种操作,如查询、修改等。 ##### 线段树的定义与特性 线段树本质上是一...

    poj1251 最小生成树

    标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...

    ACMer需要掌握的算法讲解.docx

    1. RMQ(poj3264, poj3368) 2. 并查集的高级应用(poj1703, poj2492) 3. KMP 算法(poj1961, poj2406) 4. 左偏树(可合并堆) 四、搜索 1. 最优化剪枝和可行性剪枝 2. 较为复杂的动态规划(如动态规划解特别的...

    POJ2777 个人代码

    POJ题解 个人写法 线段树每个人都不一样

Global site tag (gtag.js) - Google Analytics