果的RMQ的ST
#include <stdio.h>
#include <math.h>
int n, q;
int num[50050], dpmax[50050][20], dpmin[50050][20];
int max ( int a, int b)
{
return a>b?a:b;
}
int min ( int a, int b)
{
return a>b?b:a;
}
void creatmax()
{
int i, j;
for ( i = 1; i <= n; i++ )
dpmax[i][0] = num[i];
int k= log(n-1.0)/log(2.0);
for ( j = 1; j <= k; j++)
for ( i = 1 ; i+(1<<j)-1<=n; i++ )
dpmax[i][j] = max( dpmax[i][j-1] , dpmax[i+(1<<(j-1))][j-1] );
}
void creatmin()
{
int i, j;
for ( i = 1; i <= n; i++ )
dpmin[i][0] = num[i];
int k= log(n-1.0)/log(2.0);
for ( j = 1; j <= k; j++)
for ( i = 1 ; i+(1<<j)-1<=n; i++ )
dpmin[i][j] = min( dpmin[i][j-1] , dpmin[i+(1<<(j-1))][j-1] );
}
int getmax( int l, int r )
{
int k= log(r-l+1.0)/log(2.0);
return max(dpmax[l][k], dpmax[r-(1<<k)+1][k]);
}
int getmin( int l, int r )
{
int k= log(r-l+1.0)/log(2.0);
return min(dpmin[l][k], dpmin[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d", &n, &q);
int i, j;
for ( i = 1; i <= n; i++ )
{
scanf("%d", num+i);
}
creatmax();
creatmin();
int a, b;
while (q--)
{
scanf("%d%d", &a, &b);
printf("%d\n", getmax(a, b)-getmin(a, b));
}
return 0;
}