詢(xún)問(wèn)給定區(qū)間最大值最小值的差；
/**//*
RMQ
*/
# include <stdio.h>
# define N 50005
# define L 16
int n, m;
int h[N];
int mx[N][L], mn[N][L];
int Max(int x, int y)
{
return x > y ? x : y;
}
int Min(int x, int y)
{
return x < y ? x : y;
}
void prep(void)
{
int i, j, l;
for (j = 1, l = 1; 2*l <= n; ++j, l*=2)
for (i = 0; i+2*l <= n; ++i)
{
mx[i][j] = Max(mx[i][j-1], mx[i+l][j-1]);
mn[i][j] = Min(mn[i][j-1], mn[i+l][j-1]);
}
}
int rmq(int s, int t)
{
int j = 0, l = 1;
while (2*l <= t-s+1) ++j, l *= 2;
return Max(mx[s][j], mx[t-l+1][j]) - Min(mn[s][j], mn[t-l+1][j]);
}
void init(void)
{
int i;
scanf("%d%d", &n, &m);
for (i = 0; i < n; ++i)
{
scanf("%d", &h[i]);
mx[i][0] = mn[i][0] = h[i];
}
}
void solve(void)
{
int i, s, t;
for (i = 1; i <= m; ++i)
{
scanf("%d%d", &s, &t);
printf("%d\n", rmq(s-1, t-1));
}
}
int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
init();
prep();
solve();
return 0;
}
posted on 2012-08-27 09:06
yajunw 閱讀(125)
評(píng)論(0) 編輯 收藏 引用