[BZOJ1699][Usaco2007 Jan]Balanced Lineup排队

本文主要是介绍[BZOJ1699][Usaco2007 Jan]Balanced Lineup排队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[Usaco2007 Jan]Balanced Lineup排队

时间限制: 1 Sec 内存限制: 128 MB

题目描述

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.

输入

第1行：N,Q
第2到N+1行：每头牛的身高
第N+2到N+Q+1行：两个整数A和B，表示从A到B的所有牛。（1<=A<=B<=N）

输出

1到Q行：所有询问的回答，最高和最低的牛身高差别。

样例输入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出

6
3
0

RMQ

varx:array[0..50000]of longint;maxn,minn:array[0..50000,0..20]of longint;n,q:longint;i,j,k:longint;a,b,ans:longint;
function max(a,b:longint):longint;
beginif a>bthen exit(a)else exit(b);
end;function min(a,b:longint):longint;
beginif a<bthen exit(a)else exit(b);
end;beginreadln(n,q);for i:=1 to n doreadln(x[i]);for i:=1 to n dobeginmaxn[i,0]:=x[i];minn[i,0]:=x[i];end;for j:=1 to trunc(ln(n)/ln(2)) dofor i:=1 to n+1-(1 shl j) dobeginmaxn[i,j]:=max(maxn[i,j-1],maxn[i+(1 shl(j-1)),j-1]);minn[i,j]:=min(minn[i,j-1],minn[i+(1 shl(j-1)),j-1]);end;for i:=1 to q dobeginreadln(a,b);k:=trunc(ln(b-a+1)/ln(2));ans:=max(maxn[a,k],maxn[b-(1 shl k)+1,k])-min(minn[a,k],minn[b-(1 shl k)+1,k]);writeln(ans);end;
end.

一般线段树（TLE）

varminn,maxn:array[0..300000,1..3]of longint;x:array[0..50000]of longint;i,j,k:longint;n,m,a,b:longint;
function max(a,b:longint):longint;
beginif a>bthen exit(a)else exit(b);
end;function min(a,b:longint):longint;
beginif a<bthen exit(a)else exit(b);
end;procedure build(a,l,r:longint);
var mid:longint;
beginminn[a,1]:=l; minn[a,2]:=r; minn[a,3]:=0;maxn[a,1]:=l; maxn[a,2]:=r; maxn[a,3]:=0;if l=r then begin minn[a,3]:=x[l]; maxn[a,3]:=x[l]; exit; end;mid:=(l+r) div 2;if r<=mid then build(a*2,l,r) elseif l>mid then build(a*2+1,l,r)else begin build(a*2,l,mid); build(a*2+1,mid+1,r); end;maxn[a,3]:=max(maxn[a*2,3],maxn[a*2+1,3]);minn[a,3]:=min(minn[a*2,3],minn[a*2+1,3]);
end;function querymax(a,l,r:longint):longint;
var mid:longint;
beginif (maxn[a,1]=l)and(maxn[a,2]=r)then exit(maxn[a,3]);mid:=(maxn[a,1]+maxn[a,2])div 2;if r<=mid then exit(querymax(a*2,l,r)) elseif l>mid then exit(querymax(a*2+1,l,r))else exit(max(querymax(a*2,l,mid),querymax(a*2+1,mid+1,r)));
end;function querymin(a,l,r:longint):longint;
var mid:longint;
beginif (minn[a,1]=l)and(minn[a,2]=r)then exit(minn[a,3]);mid:=(minn[a,1]+minn[a,2])div 2;if r<=mid then exit(querymin(a*2,l,r)) elseif l>mid then exit(querymin(a*2+1,l,r))else exit(min(querymin(a*2,l,mid),querymin(a*2+1,mid+1,r)));
end;beginreadln(n,m);for i:=1 to n doreadln(x[i]);build(1,1,n);for i:=1 to m dobeginreadln(a,b);writeln(querymax(1,a,b)-querymin(1,a,b));end;
end.