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));
}
}