http://poj.org/problem?id=3264
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 #include<math.h> 6 using namespace std; 7 const int N=50005; 8 int dpmin[N][20],dpmax[N][20]; 9 int main() 10 { 11 int i,j,n,m; 12 scanf("%d%d",&n,&m); 13 memset(dpmin,0,sizeof(dpmin)); 14 memset(dpmax,0,sizeof(dpmax)); 15 for(int i=1;i<=n;i++){ 16 scanf("%d",&dpmin[i][0]); 17 dpmax[i][0]=dpmin[i][0]; 18 } 19 int mm=floor(log(1.0*n)/log(2.0)); 20 for(int j=1;j<=mm;j++){ 21 for(int i=1;i<=n;i++){ 22 if((i+(1<<(j-1)))<=n){ 23 dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]); 24 dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]); 25 } 26 } 27 } 28 int x,y; 29 for(int i=1;i<=m;i++){ 30 scanf("%d%d",&x,&y); 31 int mid=floor(log(y*1.0-x+1)/log(2.0)); 32 int maxnum=max(dpmax[x][mid],dpmax[y-(1<<mid)+1][mid]); 33 int minnum=min(dpmin[x][mid],dpmin[y-(1<<mid)+1][mid]); 34 printf("%d ",maxnum-minnum); 35 } 36 return 0; 37 }