RMQ(需要转化一下)uva11235

发布时间:2016-12-9 6:40:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"RMQ(需要转化一下)uva11235",主要涉及到RMQ(需要转化一下)uva11235方面的内容,对于RMQ(需要转化一下)uva11235感兴趣的同学可以参考一下。

思路:因为元素是连续的,所以可以把相同的元素划分成一段,用value[i]和count[i]分别表示第i段的数值和出现的次数,num[p],left[p],right[p]分别表示p位置所在的段和左右端点的编号,查询的时候只需要比较right[r]-r+1,l-left[l]+1和第num[l]!+1到num[r]-1段的最大值。RMQ数组维护的是count数组的最大值。 代码如下: #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100010; int n,q,cnt; int a[maxn],d[maxn][40]; int value[maxn],count[maxn],num[maxn],left1[maxn],right1[maxn]; void process() { int x=a[1]; cnt=1; value[1]=x;num[1]=cnt;left1[1]=1; int biao=1; for(int i=2;i<=n;i++) { if(a[i]!=x) { biao=i; value[++cnt]=a[i]; count[cnt-1]=i-left1[i-1]; x=a[i]; } num[i]=cnt; left1[i]=biao; } count[cnt]=n-left1[biao-1]; x=a[n],right1[n]=n;biao=n; for(int i=n-1;i>=1;i--) { if(a[i]!=x) biao=i,x=a[i]; right1[i]=biao; } } void RMQ_init() { int m=cnt; for(int i=1;i<=cnt;i++)d[i][0]=count[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]); } int RMQ(int l,int r) { int ans=max(right1[l]-l+1,r-left1[r]+1); int k=0; while((1<<(k+1))<=num[r]-num[l]-1)k++; return max(ans,max(d[num[l]+1][k],d[num[r]-(1<<k)][k])); } int main() { int l,r; while(cin>>n,n) { cin>>q; for(int i=1;i<=n;i++) cin>>a[i]; process(); RMQ_init(); while(q--) { cin>>l>>r; if(num[l]==num[r]){cout<<r-l+1<<endl;continue;} if(num[r]-num[l]==1){cout<<max(right1[l]-l+1,r-left1[r]+1)<<endl;} else cout<<RMQ(l,r)<<endl; } } return 0; }

上一篇:使用概要文件简化 WebSphere Application Server 管理
下一篇:黑马程序员_java运算入门

相关文章

相关评论