首页 > 其他 > 详细

RMQ问题

时间:2018-07-13 12:59:58      阅读:37      评论:0      收藏:0      [点我收藏+]

标签:scanf   std   nbsp   using   long   img   ostream   \n   log   

现给你n(<=1000000)个整数(都小于longint),有k(0< k<= 1000000)个询问,对于每个询问(L,R),回答(L,R)内的最大值为多少?

 

技术分享图片
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXARR=1000005;
const int MAXLOG=(int)log2(MAXARR)+5;

int n,askn;
int dp[MAXARR][MAXLOG];
int a[MAXARR];
int maxlogn;

void init(){
    for(int i=1;i<=n;i++){
        dp[i][0]=a[i];
    }
    for(int j=1;j<=maxlogn;j++){
        for(int i=1;i+int(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+int(1<<(j-1))][j-1]);
        }
    }
}

int ask(int l,int r){
    int len=r-l+1;
    int p=log2(len/2)+1;
    return max(dp[l][p],dp[r-int(1<<p)+1][p]);
}

int main(){
    cin>>n>>askn;
    maxlogn=log2(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    init();
    for(int i=1;i<=askn;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        printf("%d\n",ask(t1,t2));
    }
    return 0;
}
View Code

 

RMQ问题

标签:scanf   std   nbsp   using   long   img   ostream   \n   log   

原文:https://www.cnblogs.com/sun123zxy/p/rmq.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号