题解 SP1684 【FREQUENT - Frequent values】

题意

多组测试数据。

给你n个数, 以非递减的顺序给出。

再给你q个询问,

每个询问给你两个数a b。

查询a b区间内的众数的出现次数。

题解

给大家介绍一种比较简单的方法——使用st表。

st表用于区间最值查询（RMQ），是运用于静态区间的求最值。st表的方法非常简单，先预处理然后查询，就好了。其实st表就是一种另类的dp。

代码

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,ans;
int a[100001];
int dp[100001][26];
int mp[100001];
void sst()//st表
{
	for(int i=1;i<=n;i++) dp[i][0]=mp[i];
	int dd=(int)(log((double)(n+1))/log(2.0));
	for(int i=1;i<=dd;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			dp[j][i]=max(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
}
int ask(int x,int y)
{
	if(x>y)return 0;
    int k=(int)(log((double)(y-x+1))/log(2.0));
    return max(dp[x][k],dp[y-(1<<k)+1][k]);
}
int main()
{
	ios::sync_with_stdio(false);
	while(1)
	{
		cin>>n;
		if(n==0) return 0;
		cin>>m;
		mp[1]=1;
		for(int i=1;i<=n;i++) 
		{
			cin>>a[i];
			if(i>1) 
			{
				if(a[i]==a[i-1]) mp[i]=mp[i-1]+1;
				else mp[i]=1;
			}
		}
		sst();
		while(m--)
		{
			int x,y;
			cin>>x>>y;
			int now=x;
            while(now<=y&&a[now]==a[now-1])now++;
            cout<<max(now-x,ask(now,y))<<endl;
		} 
	}
	return 0;
}