Frequent values UVA - 11235【RMQ 区间最大值】

稍微转化一下，将若干个相同的数合并成一个区间，权值为数的个数，构成一个新的数据
将这些数据求区间最值就可以了。

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
using namespace std;
const int maxn = 2e5+50;
int n,q;
int p=0;//表示有多少个不同的数
int cnt[maxn],value[maxn];// cnt[i] 表示 第i种数的个数，value[i] 表示第i种数的数值
int num[maxn],lef[maxn],rig[maxn];//num[i] 表示 第i个数对应的是第几种数
//lef[i]表示第i个数对应的区间的左端点，rig[i] 对应右端点
int a[maxn];//第i个数是什么
int d[maxn][30];// d[i][j] 表示以 i 为起点 长度为 2^j的区间内答案
void st()
{
	memset(d,0,sizeof(d));
    for(int i=0;i<=p;i++) d[i][0] = cnt[i];
    for(int j=1;(1<<j)<=p;j++)
    {
        for(int i=1; i+(1<<j)-1<=p;i++)
        {
            d[i][j] = max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int l,int r)
{
    int ans = 0;
    if(num[l]==num[r]) return r-l+1;
    ans = max(rig[l]-l+1,r-lef[r]+1);
    int k=0;
    int L = rig[l]+1;
    int R = lef[r]-1;
    if(num[L]>num[R]) return ans;
    if(num[L]==num[R]) return max(ans,R-L+1);
    while((1<<(k+1))<=(num[R]-num[L]+1)) k++;
    return max(ans,max(d[num[L]][k],d[num[R]-(1<<k)+1][k]));
}
int main()
{
	while(sc(n)&&n)
	{
	    //cout<<"n= "<<n<<endl;
	    p=0; cl(d); cl(num);cl(lef); cl(rig);cl(value);cl(cnt);
		sc(q);
/* memset(lef,0,sizeof(lef)); for(int i=1;i<=n;i++) { printf("%d %d\n",i,lef[i]); printf("num[i] = %d left[i] = %d right[i] = %d\n",num[i],lef[i],rig[i]); }*/
		a[0]=-0x3f3f3f3f;
		for(int i=1;i<=n;i++) sc(a[i]);
		for(int i=1;i<=n;i++)
		{
			if(a[i]!=a[i-1])
			{
				value[++p]=a[i];
				cnt[p]++;
				lef[i] = i;
			}
			else
			{
				cnt[p]++;
				lef[i]=lef[i-1];
			}
			num[i] = p;
		}
	/* for(int i=1;i<=p;i++) { printf("value = %d ,count = %d\n",value[i],cnt[i]); }*/
		for(int i=1;i<=n;i++) rig[i] = lef[i] + cnt[num[i]] - 1;
/* for(int i=1;i<=n;i++) { printf("num[i] = %d left[i] = %d right[i] = %d\n",num[i],lef[i],rig[i]); } */

		st();
		while(q--)
        {
            int x,y;
            sc(x);sc(y);
            printf("%d\n",RMQ(x,y));
        }
	}

	system("pause");
	return 0;
}

/* 10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0 */