OJ题号：
洛谷2880
思路1：
线段树维护区间最大最小值。
#include<cstdio>
#include<cctype>
#include<utility>
#include<algorithm>
inline int getint() {
char ch;
bool sgn=false;
while(!isdigit(ch=getchar())) if(ch=='-') sgn=true;
int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return sgn?-x:x;
}
const int inf=0x7fffffff;
const int N=;
class SegmentTree {
#define _left <<1
#define _right <<1|1
private:
int max[N<<],min[N<<];
void push_up(const int p) {
max[p]=std::max(max[p _left],max[p _right]);
min[p]=std::min(min[p _left],min[p _right]);
}
public:
void build(const int p,const int b,const int e) {
if(b==e) {
max[p]=min[p]=getint();
return;
}
int mid=(b+e)>>;
build(p _left,b,mid);
build(p _right,mid+,e);
push_up(p);
}
std::pair<int,int> query(const int p,const int b,const int e,const int l,const int r) {
if((b==l)&&(e==r)) {
return std::make_pair(max[p],min[p]);
}
int mid=(b+e)>>;
int max=,min=inf;
if(l<=mid) {
std::pair<int,int> tmp=query(p _left,b,mid,l,std::min(mid,r));
max=std::max(max,tmp.first);
min=std::min(min,tmp.second);
}
if(r>mid) {
std::pair<int,int> tmp=query(p _right,mid+,e,std::max(mid+,l),r);
max=std::max(max,tmp.first);
min=std::min(min,tmp.second);
}
return std::make_pair(max,min);
}
};
SegmentTree t;
int main() {
int n=getint(),m=getint();
t.build(,,n);
while(m--) {
int l=getint(),r=getint();
std::pair<int,int> tmp=t.query(,,n,l,r);
printf("%d\n",tmp.first-tmp.second);
}
return ;
}
思路2：
倍增法求RMQ。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=,logN=log2(N)+;
int min[N][logN],max[N][logN];
int main() {
int n=getint(),m=getint();
for(int i=;i<=n;i++) {
min[i][]=max[i][]=getint();
}
for(int j=;j<=log2(n);j++) {
for(int i=;i<=n-(<<j)+;i++) {
min[i][j]=std::min(min[i][j-],min[i+(<<(j-))][j-]);
max[i][j]=std::max(max[i][j-],max[i+(<<(j-))][j-]);
}
}
while(m--) {
int l=getint(),r=getint();
int k=log2(r-l+);
printf("%d\n",std::max(max[l][k],max[r+-(<<k)][k])-std::min(min[l][k],min[r+-(<<k)][k]));
}
return ;
}