题目大意
给出一个非降序排列的整数数组a1,a2,..,an,你的任务是对于一系列询问(i,j),回到ai,ai+1..,aj中出现次数最多的值所出现的次数。
题解
请参看《训练指南》P198页。。。
代码
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define MAXN 100005 using namespace std; int n,t; int value[MAXN],cnt[MAXN],num[MAXN],l[MAXN],r[MAXN],a[MAXN],d[MAXN][30]; void RMQ_init() { int i,j; memset(d,0,sizeof(d)); for(i=0; i<t; i++) d[i][0]=cnt[i]; for(j=1; (1<<j)<=t; j++) for(i=0; i+(1<<j)-1<t; i++) d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]); } int RMQ(int L,int R) { int k=0; if(L>R) return 0; while((1<<(k+1))<=R-L+1) k++; return max(d[L][k],d[R-(1<<k)+1][k]); } void init() { int i,j,ans,m,k,ll,rr,maxs; while(scanf("%d",&n)&&n) { scanf("%d",&m); for(i=1; i<=n; i++) scanf("%d",&a[i]); i=1; t=0; while(i<=n) { j=i; ans=0; while(a[j]==a[i]&&j<=n) { j++; ans++; } for(k=i; k<j; k++) { num[k]=t; l[k]=i; r[k]=j-1; } value[t]=a[i]; cnt[t]=ans; t++; i=j; } RMQ_init(); while(m--) { scanf("%d%d",&ll,&rr); if(num[ll]==num[rr]) maxs=rr-ll+1; else { maxs=max(r[ll]-ll+1,rr-l[rr]+1); maxs=max(maxs,RMQ(num[ll]+1,num[rr]-1)); } printf("%d\n",maxs); } } } int main(void) { init(); return 0; }