NKLINEUP - Xếp hàng
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#include <cmath>
#define MAXN 50000+5
#define LOGMAXN 20 /*log 50000 ~ 16*/
int n, q;
int a[MAXN];
int m[MAXN][LOGMAXN], mx[MAXN][LOGMAXN];
int min( int a, int b ) { return a < b ? a : b; }
int max( int a, int b ) { return a>b?a:b; }
void preprocess() {
for( int i = 0; i < n; m[i][0] = mx[i][0] = i, ++i );
for( int j = 1; 1 << j <= n; ++j )
for( int i = 0; i + ( 1 << j ) - 1 < n; ++i ) {
m[i][j] = a[m[i][j-1]] < a[m[i+(1<<j-1)][j-1]] ? m[i][j-1] : m[i+(1<<j-1)][j-1];
mx[i][j] = a[mx[i][j-1]] > a[mx[i+(1<<j-1)][j-1]] ? mx[i][j-1] : mx[i+(1<<(j-1))][j-1];
}
}
int main() {
scanf( "%d%d", &n, &q );
for( int i = 0; i < n; scanf( "%d", &a[i++] ) );
preprocess();
for( int i = 0; i < q; ++i ) {
int i, j, k; scanf( "%d%d", &i, &j ); --i; --j; k = (int) floor(log(j-i+1)/log(2));
printf("%d\n", max(a[mx[i][k]], a[mx[j-(1<<k)+1][k]]) - min(a[m[i][k]], a[m[j-(1<<k)+1][k]]));
}
return 0;
}