【RMQ(倍增算法)模版】

love

[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[i][0]);
		Max[i][0]=Min[i][0];
	}
	for(int j=1;j<=floor(log2(n));j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
			Min[i][j]=min(Min[i][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）的区间的极值