【RMQ(倍增算法)模版】
本帖最后由 love 于 2018-6-14 13:57 编辑#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int Min,Max;
int main(){
int a,b;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&Min);
Max=Min;
}
for(int j=1;j<=floor(log2(n));j++){
for(int i=1;i<=n-(1<<j)+1;i++){
Max=max(Max,Max);
Min=min(Min,Min);
}
}
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
int k=floor(log2(b-a+1));
printf("%d\n",max(Max,Max)-min(Min,Min));
}
}
注意数组含义：Min表示从第i个点开始，连续的长度为（1<<j）的区间的极值
页:
[1]