APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

HDU 1806 Frequent values(区间RMQ问题)题解

2018年11月3日 1309点热度 0人点赞 0条评论

洛谷:https://www.luogu.org/problemnew/show/U50167

Description

给定一个非降序的由 n 个整数构成的序列以及 q 个由整数i 和 j 构成的询问。对于每一个询问,输出在 a[i],a[i+1], ... ,a[j-1],a[j]里面出现次数最多的那个(些)整数出现的次数。

Input

第一行包含两个整数, n 和 q。第二行包括 n 个整数 a[1],a[2], ... ,a[n],由空格分开。以下 q 行每一行包括一个询问,一个询问由两个整数 i 和 j 构成, i 和 j 指示询问索引的边界。 保证 i<=j。

Output

对于每一组询问,输出一行一个整数:在给定区间内出现次数最多的那个(些)整数出现的次数。

Sample Input

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10

Sample Output

1 4 3

解析及代码

暴力:

我们考虑暴力解法,根据题意模拟即可,复杂度\(O(qn^2)\)(不计算Map复杂度)

void baoli() {
	for(int i = 1;i <= m;++i) {
		int l,r,ans = 0;
		map <int ,int > M;
		scanf("%d%d",&l,&r);
		for(int j = l;j <= r;++j) M[a[j]]++,ans = max(ans,M[a[j]]);
		printf("%d\n",ans);
	}
}

正解①:

考虑用ST表维护区间内每个数出现的次数。对于区间l,r,我们可以分为l ->a[l]最后出现的地方 和a[r]一开始出现的地方->r 以及 a[l]最后出现的地方+1到a[r]最开始出现的地方-1三个区间。

对于第一个和第二个区间。我们暴力查找,通过二分将我们需要的a[r]一开始出现的地方 及 a[l]最后出现的地方。倘若l仍然小于r我们在查找满区间(没有被l,r分割的区间),这样我们就得到了\(O(qlogn)\)的算法。可以通过本题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std; 

const int MAXN = 100005;

int a[MAXN];
int lg[MAXN];
int Max[MAXN][22];
int n,Num = 1,m; 

void Init() {
	lg[0] = -1;
	for(int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j <= 21;++j)	
		for(int i = 1;i + (1 << j) - 1 <= n;++i)	
			Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]);
}

int Query(int l,int r) {
	int k = lg[r - l + 1];
	return max(Max[l][k],Max[r - (1 << k) + 1][k]);
}

int main() {
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) scanf("%d",a + i);
	for(int i = 1;i <= n;++i) {
		if(a[i] == a[i + 1]) Num++;
		else Num = 1;
		Max[i][0] = Num; //到达每一个点时每一个数的最大出现次数 
	}
	Init();
	for(int i = 1;i <= m;++i) {
		int l,r;
		scanf("%d%d",&l,&r); //分段 分l->a[l]最后出现的位置 a[r]一开始出现的位置->r  和  完整的区间进行ST查询 
		int pos2 = lower_bound(a + 1,a + 1 + n,a[r]) - a; // 返回当前a[r]一开始出现的位置
		if(a[pos2] != a[r]) pos2++; 
		if(pos2 < l) pos2 = l; //特判一下,如果a[r]一开始出现的位置比l小,我们是不可取pos2的 
		int Ans = r - pos2 + 1; //一开始定义Ans为a[r]出现的次数 
		r = pos2 - 1; //找下一个完整区间的数 
		if(l > r) { //如果l比r大了,那么我们找完了所有区间 
			printf("%d\n",Ans);
			continue;
		}
		int pos1 = upper_bound(a + 1,a + 1 + n,a[l]) - a; //返回当前a[l]最后出现的位置
		if(a[pos1] != a[l]) pos1--; 
		Ans = max(Ans,pos1 - l + 1); //将两个单独的区间取max 
		//cout << pos1 << " " << pos2 << endl << endl;
		l = pos1 + 1;
		if(l > r) { //如果l比r还大,那么我们已经找完了所有区间 
			printf("%d\n",Ans);
			continue;
		}
		Ans = max(Ans,Query(l,r));  //否则我们寻找完整的区间进行ST 
		printf("%d\n",Ans);
	}
	return 0;
}

正解②:

在维护到达每一个点时每一个数的最大出现次数 时,我们可以倒序枚举,这样就不用管开头的区间了,因为保证了单调递增,这样我们RMQ查询时默认肯定会到达a[l]的最大值的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std; 

const int MAXN = 100005;

int a[MAXN];
int lg[MAXN];
int Max[MAXN][22];
int n,Num = 1,m; 

void Init() {
	lg[0] = -1;
	for(int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j <= 21;++j)	
		for(int i = 1;i + (1 << j) - 1 <= n;++i)	
			Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]);
}

int Query(int l,int r) {
	int k = lg[r - l + 1];
	return max(Max[l][k],Max[r - (1 << k) + 1][k]);
}

int main() {
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) scanf("%d",a + i);
	for(int i = n;i >= 1;--i) {
		if(a[i] == a[i + 1]) Num++;
		else Num = 1;
		Max[i][0] = Num; //到达每一个点时每一个数的最大出现次数 
	}
	Init();
	for(int i = 1;i <= m;++i) {
		int l,r;
		scanf("%d%d",&l,&r); //分段 分l->a[l]最后出现的位置 a[r]一开始出现的位置->r  和  完整的区间进行ST查询 
		int pos2 = lower_bound(a + 1,a + 1 + n,a[r]) - a; // 返回当前a[r]一开始出现的位置
		if(pos2 < l) pos2 = l; //特判一下,如果a[r]一开始出现的位置比l小,我们是不可取pos2的 
		//if(i == m) cout << l << " " << r << " " << pos2 << endl;
		int Ans = r - pos2 + 1; //一开始定义Ans为a[r]出现的次数 
		r = pos2 - 1; //找下一个完整区间的数 
		if(l > r) { //如果l比r大了,那么我们找完了所有区间 
			printf("%d\n",Ans);
			continue;
		}
		Ans = max(Ans,Query(l,r));  //否则我们寻找完整的区间进行ST 
		printf("%d\n",Ans);
	}
	return 0;
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: HDU logn OI RIP RMQ ST ST表 模拟 洛谷 算法
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
2020/01/28:MMPI临床量表测量结果 C++程序查看运行时间&&空间大小&&程序运行分析 教你如何观看性感荷官在线发牌 Pornhub风格Logo生成器 几种云端 VSCode/类 VSCode 方案对比与部署 先有华为后有天,不买华为是汉奸
标签聚合
C++ OI C/C++ ST 日常 动漫 洛谷 HTML
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang