一 题意:给定递增序列,找出连续出现的最长子序列,然后求出它的长度,即最高频率。注意必须是连续出现。
二 算法:可以事先求出序列中每个数字的最高频率,比如序列(-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 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...
线段树的构建通常分为两个阶段:初始化和构造。初始化时,我们将原始数组中的元素逐个放入线段树的叶子节点。构造阶段则是通过一系列的合并操作,自底向上建立线段树的非叶节点。线段树的每个节点保存的信息可能包括...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
// 初始化线段树和懒标签数组 // ... } 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 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...
在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...
在本题目"Frequent Values (poj 3368)"中,我们需要解决的是一个与数据处理和算法相关的编程问题。该题目是广东工业大学《算法和高级数据结构教程课程设计》的一部分,采用C语言进行实现。下面我们将深入探讨这个...
- **POJ 1151**:结合了线段树和离散化的技巧来求解矩形面积的并集。这需要对输入的坐标进行离散化处理,以减少空间复杂度,并使用线段树维护区间信息。 - **POJ 1177**:求解矩形周长的并集。此题与POJ 1151类似,...
poj 2763 程序 线段树 LCA 2000MS AC
* RMQ:POJ3264、POJ3368 * 并查集的高级应用:POJ1703、POJ2492 * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ...
10. **POJ 2528 线段树.txt**:这是第三个线段树相关的题目,解题报告可能会深入讲解线段树在不同场景下的应用。 通过阅读这些解题报告,你可以学习到各种高级算法的应用,如动态规划、搜索算法、数据结构(如线段...
* RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 poj1703、poj2492。 * KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 *...
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
- RMQ(区间查询):如`poj3264, poj3368`。 - 并查集的高级应用:如`poj1703, poj2492`。 - **搜索** - 最优化剪枝和可行性剪枝:如`poj3411, poj1724`。 - **动态规划** - 复杂的动态规划:如`poj1191, poj...
### ACM数据结构之树状数组和线段树 #### 线段树 线段树是一种非常有效的数据结构,主要用于解决区间查询问题。它能够快速地处理区间内的各种操作,如查询、修改等。 ##### 线段树的定义与特性 线段树本质上是一...
标题“poj1251 最小生成树”是一个编程竞赛题目,来源于著名的在线编程平台POJ(Programming Online Judge)。这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,...
1. RMQ(poj3264, poj3368) 2. 并查集的高级应用(poj1703, poj2492) 3. KMP 算法(poj1961, poj2406) 4. 左偏树(可合并堆) 四、搜索 1. 最优化剪枝和可行性剪枝 2. 较为复杂的动态规划(如动态规划解特别的...
POJ题解 个人写法 线段树每个人都不一样