描述 Description
每天, 农夫 John 的 N(1 <= N <= 50,000) 头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊, 牛的身高不应该相差太大. John 准备了 Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.
输入格式 InputFormat
第一行: N 和 Q. * 第 2..N+1 行: 第 i+1 行是第 i 头牛的身高.
第 N+2..N+Q+1 行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从 A 到 B 的所有牛.
输出格式 OutputFormat
第 1..Q 行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.
样例输入 SampleInput
6 3
1
7
3
4
2
5
1 5
4 6
2 2
样例输出 SampleOutput
6
3
0
来源 Source
Gold
代码 Code
线段树或者 RMQ. 加上快速读入。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ls(x) x<<1
#define rs(x) (x<<1)+1
const int inf=0x7fffffff;
struct tnode
{
int l,r,maxs,mins;
}tree[200005];
int a[50005];
int i,j,t,n,m,q,k,z,y,x,amax,amin;
inline int read()
{
int x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void build(int s,int tl,int tr)
{
int i,j,t,mid;
tree[s].l=tl;tree[s].r=tr;
if (tl==tr)
{
tree[s].maxs=tree[s].mins=a[tl];
return ;
}
mid=(tl+tr)>>1;
build(ls(s),tl,mid);build(rs(s),mid+1,tr);
tree[s].maxs=max(tree[ls(s)].maxs,tree[rs(s)].maxs);
tree[s].mins=min(tree[ls(s)].mins,tree[rs(s)].mins);
}
void find(int s,int tl,int tr)
{
int i,j,t,mid;
if (tree[s].l>=tl && tree[s].r<=tr)
{
amax=max(amax,tree[s].maxs);
amin=min(amin,tree[s].mins);
return ;
}
mid=(tree[s].l+tree[s].r)>>1;
if (tr<=mid) find(ls(s),tl,tr);
else if (tl>mid) find(rs(s),tl,tr);
else
{
find(ls(s),tl,mid);
find(rs(s),mid+1,tr);
}
}
int main()
{
n=read();q=read();
for (i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for (i=1;i<=q;i++)
{
x=read();y=read();
amin=inf;amax=-inf;
find(1,x,y);
printf("%d\n",amax-amin);
}
return 0;
}