询问给定区间最大值最小值的差;
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
RMQ
*/
# include <stdio.h>
![](/Images/OutliningIndicators/None.gif)
# define N 50005
# define L 16
![](/Images/OutliningIndicators/None.gif)
int n, m;
int h[N];
int mx[N][L], mn[N][L];
![](/Images/OutliningIndicators/None.gif)
int Max(int x, int y)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
return x > y ? x : y;
}
![](/Images/OutliningIndicators/None.gif)
int Min(int x, int y)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
return x < y ? x : y;
}
![](/Images/OutliningIndicators/None.gif)
void prep(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, j, l;
for (j = 1, l = 1; 2*l <= n; ++j, l*=2)
for (i = 0; i+2*l <= n; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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]);
}
}
![](/Images/OutliningIndicators/None.gif)
int rmq(int s, int t)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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]);
}
![](/Images/OutliningIndicators/None.gif)
void init(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
scanf("%d%d", &n, &m);
for (i = 0; i < n; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d", &h[i]);
mx[i][0] = mn[i][0] = h[i];
}
}
![](/Images/OutliningIndicators/None.gif)
void solve(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, s, t;
for (i = 1; i <= m; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d", &s, &t);
printf("%d\n", rmq(s-1, t-1));
}
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
![](/Images/OutliningIndicators/InBlock.gif)
init();
prep();
solve();
![](/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](/Images/OutliningIndicators/None.gif)
posted on 2012-08-27 09:06
yajunw 阅读(114)
评论(0) 编辑 收藏 引用