重工电子论坛

标题: 【RMQ(倍增算法)模版】 [打印本页]

作者: love    时间: 2018-6-13 23:06
标题: 【RMQ(倍增算法)模版】
本帖最后由 love 于 2018-6-14 13:57 编辑

[AppleScript] syntaxhighlighter_viewsource syntaxhighlighter_copycode

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int Min[50001][32],Max[50001][32];
int main(){
        int a,b;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
                scanf("%d",&Min[0]);
                Max[0]=Min[0];
        }
        for(int j=1;j<=floor(log2(n));j++){
                for(int i=1;i<=n-(1<<j)+1;i++){
                        Max[j]=max(Max[j-1],Max[i+(1<<(j-1))][j-1]);
                        Min[j]=min(Min[j-1],Min[i+(1<<(j-1))][j-1]);
                }
        }
        for(int i=1;i<=m;i++){
                scanf("%d%d",&a,&b);
                int k=floor(log2(b-a+1));
                printf("%d\n",max(Max[a][k],Max[b-(1<<k)+1][k])-min(Min[a][k],Min[b-(1<<k)+1][k]));
        }
}

注意数组含义:Min[j]表示从第i个点开始,连续的长度为(1<<j)的区间的极值




欢迎光临 重工电子论坛 (http://cqutlab.cn/) Powered by Discuz! X3.1