poj3264 Balanced Lineup(RMQ)

poj3264

题目

有一堆牛，牛有身高，求一个区间里最高牛和最低牛身高之差。

思路

很裸的题，可做模版。

代码

#include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> using namespace std; int mmin[50010][20]; int mmax[50010][20]; void rmq_st(int n) { for(int i=0; i<n; i++) { scanf("%d",&mmin[i][0]); mmax[i][0]=mmin[i][0]; } int endj=(int)(log(n+0.0)/log(2.0)); for(int j=1; j<=endj; j++) { int endi=n+1-(1<<j); for(int i=0; i<endi; i++) { mmin[i][j]=min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]); mmax[i][j]=max(mmax[i][j-1],mmax[i+(1<<(j-1))][j-1]); } } } int query_min(int l,int r) { int k=(int)(log(r-l+1.0)/log(2.0)); return min(mmin[l][k],mmin[r-(1<<k)+1][k]); } int query_max(int l,int r) { int k=(int)(log(r-l+1.0)/log(2.0)); return max(mmax[l][k],mmax[r-(1<<k)+1][k]); } int main() { int n,q; scanf("%d %d",&n,&q); rmq_st(n); for(int i=0; i<q; i++) { int a,b; scanf("%d %d",&a,&b); a--; b--; printf("%d\n",query_max(a,b)-query_min(a,b)); } return 0; }