BZOJ 1699 [Usaco2007 Jan]Balanced Lineup排队 线段树

题意:链接方法:线段树解析:题意即题解。多次询问区间最大值与最小值的差，，显然直接上线段树或者rmq维护区间最值即可。代码:;int n,q;int ma[N<<2],mi[N<<2],dis[N<<2];void init(){memset(ma,-1,sizeof(ma));memset(mi,0x3f,sizeof(mi));}void pushup(int rt){ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);}void build(int l,int r,int rt){if(l==r){int x;scanf(“%d”,&x);ma[rt]=mi[rt]=x;return;}int mid=(l+r)>>1;build(lson),build(rson);pushup(rt);}pa query(int L,int R,int l,int r,int rt){pa ret;ret.first=-1,ret.second=0x3f3f3f3f;if(L<=l&&r<=R){pa p;p.first=ma[rt],p.second=mi[rt];return p;}int mid=(l+r)>>1;if(L<=mid){pa tmp=query(L,R,lson);ret.first=max(ret.first,tmp.first),ret.second=min(ret.second,tmp.second);}if(R>mid){pa tmp=query(L,R,rson);ret.first=max(ret.first,tmp.first),ret.second=min(ret.second,tmp.second);}return ret;}int main(){init();scanf(“%d%d”,&n,&q);build(1,n,1);for(int i=1;i<=q;i++){int x,y;scanf(“%d%d”,&x,&y);pa tmp=query(x,y,1,n,1);printf(“%d\n”,tmp.first-tmp.second);}}

旅游不在乎终点，而是在意途中的人和事还有那些美好的记忆和景色。