poj3368 Frequent values(ST思维题)

最新推荐文章于 2022-04-11 20:11:05 发布

小衣同学

最新推荐文章于 2022-04-11 20:11:05 发布

阅读量326

点赞数

分类专栏： # 倍增/RMQ((ST/二维ST/二维线段树/KD树) 文章标签： ST表 RMQ

本文链接：https://blog.csdn.net/Code92007/article/details/89386688

版权

倍增/RMQ((ST/二维ST/二维线段树/KD树) 专栏收录该内容

10 篇文章

订阅专栏

题目

有n(n<=1e5)个数字，m(m<=1e5)次询问，

每次询问区间[Li,Ri]中出现最多次数的数字，输出最多次数。

题目保证，对于 $1<=i<=n,a_{i}<=a_{i+1}$

思路来源

https://blog.csdn.net/qq_24489717/article/details/51040122

题解

首先，尺取处理出，对于值v来说，它是第几个出现的v

由于数组是不降的，所以相同的值是挨在一起的

这样处理之后，就可以把询问区间分成两段了，

比如对于出现次数3 4 1 2 1 2 3 1 2 1这样的区间

只有第一个3 4是没有包含区间左端点的，所以，

答案是左边相同的值的区间[3,4]的区间长度和[1 2 1 2 3 1 2 1]区间的最大值

这个临界点可以二分，二分出来最大的和a[l]相同的值的下标

注意特判，区间只有一个值的情形

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
using namespace std;
const int maxn=1e6+10;
int mx[maxn][22];
int n,m;
int a[maxn],num[maxn];
int l,r,pos,ans;
void ST(int n)
{
	for(int i=1;i<=n;++i)
	mx[i][0]=num[i];
	for(int len=1;(1<<len)<=n;++len)
	{
		for(int i=1;i+(1<<len)-1<=n;i++)
		mx[i][len]=max(mx[i][len-1],mx[i+(1<<(len-1))][len-1]);
	}
}
int RMQ(int l,int r)
{
	int len=log(r-l+1)/log(2);
	return max(mx[l][len],mx[r-(1<<len)+1][len]);
}
int erfen(int l,int r)//最大的==a[l]的下标 
{
	int v=a[l];
	while(l<r)
	{
		int mid=(l+r)/2;
		if(a[mid]==v)l=mid+1;
		else r=mid;
	}
	if(a[l]!=v)l--;
	return l;
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		//num[0]=a[0]=0 默认 
		scanf("%d",&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[i]=num[i-1]+1;//尺取 连续子段长度 
			else num[i]=1;
		}
		ST(n);
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d",&l,&r);
			pos=erfen(l,r);//[l,pos],[pos+1,r]
			if(pos==r)ans=r-l+1;
			else ans=max(pos-l+1,RMQ(pos+1,r));
			printf("%d\n",ans); 
		}
	}
	return 0;
}