poj 3264 Balanced Lineup（查询区间最大值与最小值的差）

1.代码： ~~~ #include<stdio.h> #include<string.h> #include<math.h> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define N 100000 int a[N]; int ST1[N][20]; int ST2[N][20]; int n,q; void make_ST() { for(int j=1;(1<<j)<=n;j++) { for(int i=1;(i+(1<<j)-1)<=n;i++) { ST1[i][j]=Max(ST1[i][j-1],ST1[i+(1<<(j-1))][j-1]); ST2[i][j]=Min(ST2[i][j-1],ST2[i+(1<<(j-1))][j-1]); } } } int Query(int l,int r) { int k=floor(log((double)(r-l+1))/log((double)(2))); return Max(ST1[l][k],ST1[r-(1<<k)+1][k])-Min(ST2[l][k],ST2[r-(1<<k)+1][k]); } int main() { while(scanf("%d%d",&n,&q)==2) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); ST1[i][0]=ST2[i][0]=a[i]; } make_ST(); while(q--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",Query(l,r)); } } return 0; } ~~~