Posted on 2010-11-05 23:41
acronix 阅读(495)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai收集的模板
//rmq 求得最大最小值的序号。
// 注意位运算优先级比+低。
//被字母（l）和 数字（1）搞了半天，最后终于看出来了
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 50005;
int rmqMin[MAX][20],rmqMax[MAX][20];
int n,q;
void make_rmq(int len,int a[])
{
int i,j,k,x1,y1,x2,y2;
for (i = 1; i <= len; i++)
rmqMin[i][0] = rmqMax[i][0] = i;
for (j = 1; (1 << j) <= len; j++)
for (i = 1; i + (1 << j) - 1 <= len; i++)
{
x1 = rmqMin[i][j-1];
y1 = rmqMin[i + (1<<(j-1))][j-1];
x2 = rmqMax[i][j-1];
y2 = rmqMax[i + (1<<(j-1))][j-1];
rmqMin[i][j] = a[x1] < a[y1] ? x1 : y1;
rmqMax[i][j] = a[x2] > a[y2] ? x2 : y2;
}
}
int query_min(int lf,int rt,int a[])
{
int d = rt - lf + 1,k = 0,x,y;
while ((1<<(k+1)) < d)
k ++;
x = rmqMin[lf][k];
y = rmqMin[rt - (1 << k) + 1][k];
return a[x] < a[y] ? x : y;
}
int query_max(int lf,int rt,int a[])
{
int d = rt - lf + 1, k = 0, x, y;
while ((1<<(k+1)) < d)
k++;
x = rmqMax[lf][k];
y = rmqMax[rt - (1<<k) + 1][k];
return a[x] > a[y] ? x : y;
}
int main()
{
int he[MAX],i,lf,rt;
while (scanf("%d %d", &n, &q) != EOF)
{
for (i = 1; i <= n ; i++)
scanf("%d", &he[i]);
make_rmq(n,he);
for (i = 1; i <= q; i++)
{
scanf("%d %d", &lf, &rt);
printf("%d\n",he[query_max(lf,rt,he)] - he[query_min(lf,rt,he)]);
}
}
return 0;
}