poj Balanced Lineup

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

http://poj.org/problem?id=3264

线段树板子题，由原来的维护区间和变成维护区间最大值和最小值即可。

#include<iostream>
using namespace std;
typedef long long ll;
#define maxn 50007  
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
int mmax,mmin;
struct T{int mmax;int mmin;
};
T Sum[maxn<<2];
int A[maxn],n;//存原数组数据下标[1,n]  
void PushUp(int rt){Sum[rt].mmax=max(Sum[rt<<1].mmax,Sum[rt<<1|1].mmax);Sum[rt].mmin=min(Sum[rt<<1].mmin,Sum[rt<<1|1].mmin);
}
void CreatTree(int l,int r,int rt) {if(l==r){Sum[rt].mmax=A[l];Sum[rt].mmin=A[l];} else{int mid=(l+r)>>1;CreatTree(l,mid,rt<<1);CreatTree(mid+1,r,rt<<1|1);PushUp(rt);}
} 
void QueryMaxMin(int L,int R,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号if(L <= l && r <= R){mmax=max(Sum[rt].mmax,mmax);mmin=min(Sum[rt].mmin,mmin);return ;}int m=(l+r)>>1;if(L <= m){QueryMaxMin(L,R,l,m,rt<<1);} if(R >  m){QueryMaxMin(L,R,m+1,r,rt<<1|1);} }
int num,N;
int main(){scanf("%d%d",&num,&N);for(int i=1;i<=num;++i){scanf("%d",A+i);}CreatTree(1,num,1);int l,r; while(N--) {scanf("%d%d",&l,&r);mmax=-1;mmin=1e9+5;QueryMaxMin(l,r,1,num,1);cout<<mmax-mmin<<endl;} return 0;
}

 

这篇关于poj Balanced Lineup的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---