欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

RMQ模板(ST表)

程序员文章站 2024-01-14 13:49:52
...
#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;
int mx[50005][22],mn[50005][22];
int l,r,v;

void st(int n){
	for(int l=1;(1<<l)<=n;l++){
		for(int i=1;i+(1<<l)-1<=n;i++){
			mx[i][l]=max(mx[i][l-1],mx[i+(1<<(l-1))][l-1]);
			mn[i][l]=min(mn[i][l-1],mn[i+(1<<(l-1))][l-1]);
		}
	}
}

int RMQ(int l,int r,int w)
{
	int k=log(r-l+1)/log(2);
	int ans;
	if(!w)ans=max(mx[l][k],mx[r-(1<<k)+1][k]);
	else ans=min(mn[l][k],mn[r-(1<<k)+1][k]);
	return ans;
}

int main(){
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		mx[i][0]=mn[i][0]=t;
	}
	
	st(n);
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		
		printf("%d\n",RMQ(l,r,0)-RMQ(l,r,1));
	}
}