poj3368 Frequent values（rmq）

poj3368

题目

给一个非严格递增的序列，求某个区间段出现频率次数最多数的频率数

思路

强行rmq，因为是按从小到大给的，在读入的时候可以把当前位的值给成当前数字出现了几次，但仅仅这样会有问题，像-1 -1 1 1时，询问2~3区间时结果是2，所以我开了个right数组，倒着遍历了一边，把每一个值赋成当前数字结束位的序号，在对于每一个询问，我先把L~right(L)处理掉（也就是min(R,right[L])-L+1）再用rmq询问（right(L)+1）~R的最值取二者最大的即可。

代码

#include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> using namespace std; int f[100010],right[100010]; int mmax[100010][20]; int pre; void rmq_st(int n) { for(int i=0; i<n; i++) { int p; scanf("%d",&p); if(i==0) { mmax[i][0]=1; pre=p; } else { if(p==pre) { mmax[i][0]=mmax[i-1][0]+1; } else { mmax[i][0]=1; } pre=p; } } int endj=(int)(log(n+0.0)/log(2.0)); for(int j=1; j<=endj; j++) { int endi=n+1-(1<<j); for(int i=0; i<endi; i++) { mmax[i][j]=max(mmax[i][j-1],mmax[i+(1<<(j-1))][j-1]); } } } int query_max(int l,int r) { int k=(int)(log(r-l+1.0)/log(2.0)); return max(mmax[l][k],mmax[r-(1<<k)+1][k]); } int main() { int n,q; while(scanf("%d",&n)&&n) { scanf("%d",&q); rmq_st(n); int ri=n-1; for(int i=n-1; i>=0; i--) { if(mmax[i][0]==1) { right[i]=ri; ri=i-1; } else { right[i]=ri; } } int ans; for(int i=0; i<q; i++) { int l,r; scanf("%d %d",&l,&r); l--; r--; ans=min(r,right[l])-l+1; if(right[l]<r) { //printf("%d\n",query_max(right[l]+1,r)); ans=max(ans,query_max(right[l]+1,r)); } printf("%d\n",ans); } } return 0; }