poj 3264 RMQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=5e4+9;
int maxrmq[maxn][20],minrmq[maxn][20],a[maxn];
int n,q;
void getrmq()
{
for(int i=1;i<=n;i++)
minrmq[i][0]=maxrmq[i][0]=a[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
{
maxrmq[j][i]=max(maxrmq[j][i-1],maxrmq[j+(1<<i-1)][i-1]);
minrmq[j][i]=min(minrmq[j][i-1],minrmq[j+(1<<i-1)][i-1]);
}
}
int askrmq(int t,int s)
{
int k=log(s-t+1)/log(2);
int mmax=max(maxrmq[t][k],maxrmq[s-(1<<k)+1][k]);
int mmin=min(minrmq[t][k],minrmq[s-(1<<k)+1][k]);
return mmax-mmin;
}
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d %d",&n,&q)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
getrmq();
for(int i=1,t,s;i<=q;i++)
{
scanf("%d %d",&t,&s);
printf("%d\n",askrmq(t,s));
}
}
return 0;
}
补充：软件开发 , C++ ,
