poj 3264 Balanced Lineup (线段树)

poj 3264 Balanced Lineup (线段树)

题意：#include#include#includeusing namespace std;const int maxn=5e4+5;int height[maxn];// 最长区间长度struct node{ int left,right,high,low;}btree[3*maxn]; // 设置根节点下标是1，则左孩子是2*dex,右孩子下标是2*dex+1.void build(int root,int l,int r){ //主函数数组里的dex对应这里的l,r btree[root].left=l; //root对应树和各种子树的根节点 btree[root].right=r; if(l==r){ btree[root].low=btree[root].high=height[l]; return ; } int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); btree[root].high=max(btree[2*root].high,btree[2*root+1].high); //递归回溯赋值给双亲结点 btree[root].low=min(btree[2*root].low,btree[2*root+1].low);}void query(int root,int L,int R,int &higher,int &lower){ if(L<=btree[root].left&&R>=btree[root].right){ higher=max(btree[root].high,higher); lower=min(btree[root].low,lower); return ; } int mid=(btree[root].left+btree[root].right)/2; if(L<=mid)query(root*2,L,R,higher,lower); // L,R不要弄错，否则会数组越界 if(R>mid)query(2*root+1,L,R,higher,lower);}int main(int argc, char *argv[]) { //freopen("cin.txt","r",stdin); int N,Q,i; while(cin>>N>>Q){ for(i=1;i<=N;i++)scanf("%d",&height[i]); build(1,1,N); for(i=1;i<=Q;i++){ int a,b,higher=0,lower=(int)(1e6+1); scanf("%d%d",&a,&b); query(1,a,b,higher,lower); printf("%d\n",higher-lower); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。