APTX部落

  • ACGN
  • Coding
  • WebServer
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By Mizuki
  1. 首页
  2. OI
  3. 正文

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

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

文章目录[隐藏]

  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • 解析及代码

洛谷: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;
}

 

标签: HDU logn OI RIP RMQ ST ST表 模拟 洛谷 算法
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 React 配合后端热更新
恭喜四叶小天使取得最后的胜利 Nginx:301永久重定向配置以及自动跳转https配置 Pornhub风格Logo生成器 C++快速幂 #动漫#路人女主的养成方法第二季 1080P Windows 10 Enterprise LTSC 2019 OEM 在线激活
标签聚合
ST HTML 洛谷 OI C++ 动漫 C/C++ 日常
分类
  • ACGN
  • Coding
  • Daily
  • OI
  • Share
  • WebServer

COPYRIGHT © 2022 APTX部落. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang