首页 > 代码库 > Uva11235 Frequent values (RMQ)
Uva11235 Frequent values (RMQ)
///对于每个询问(l,r),分为两个部分,前半部分求与l之前相同的数的个数直到t,后半部分从t开始直接用RMQ求解最大值就行了。 ///最后结果为max(前半部分,后半部分)。 # include <algorithm> # include <string.h> # include <math.h> # include <iostream> using namespace std; int f[100100];///前i个有多少个相同的数 int dp[100100][20]; int n; void RMQ_init() { for(int i=1; i<=n; i++) dp[i][0]=f[i]; int k=(int)(log(n+1.0)/log(2.0)); for(int j=1; j<=k; j++) for(int i=1; i+(1<<j)-1<=n; i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int RMQ(int L,int R)///查询 { if(L>R) return 0; int k=(int)(log(R-L+1.0)/log(2.0)); return max(dp[L][k],dp[R-(1<<k)+1][k]); } int main() { int q,i,a[100100],l,r; while(~scanf("%d",&n),n) { scanf("%d",&q); for(i=1; i<=n; i++) scanf("%d",&a[i]); for(i=1; i<=n; i++) { if(i==1) f[i]=1; else { if(a[i]==a[i-1]) f[i]=f[i-1]+1; else f[i]=1; } } RMQ_init(); while(q--) { scanf("%d%d",&l,&r); int t=l; while(t<=r&&a[t]==a[t-1]) t++; int ans=RMQ(t,r); int cnt=max(ans,t-l); printf("%d\n",cnt); } } return 0; }
Uva11235 Frequent values (RMQ)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。