poj 3264——Balanced Lineup

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

线段树

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 50004
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((t[rt].l+t[rt].r)>>1)
struct tree
{int l,r;int max,min;
}t[maxn<<2];
int n,m;
void pushup(int rt)
{t[rt].max=max(t[ls].max,t[rs].max);t[rt].min=min(t[ls].min,t[rs].min);
}
void build(int rt,int l,int r)
{t[rt].l=l;t[rt].r=r;if(l==r){	int x;scanf("%d",&x);t[rt].max=x;t[rt].min=x;return ;}build(ls,l,mid);build(rs,mid+1,r);pushup(rt);
}
int query_max(int rt,int l,int r)
{if(t[rt].l==l&&t[rt].r==r)return t[rt].max;if(r<=mid)return query_max(ls,l,r);else if(l>mid)return query_max(rs,l,r);elsereturn max(query_max(ls,l,mid),query_max(rs,mid+1,r));
}
int query_min(int rt,int l,int r)
{if(t[rt].l==l&&t[rt].r==r)return t[rt].min;if(r<=mid)return query_min(ls,l,r);else if(l>mid)return query_min(rs,l,r);elsereturn min(query_min(ls,l,mid),query_min(rs,mid+1,r));
}
int query(int l,int r)
{return query_max(1,l,r)-query_min(1,l,r);
}
int main()
{while(~scanf("%d%d",&n,&m)){build(1,1,n);int l,r;while(m--){scanf("%d%d",&l,&r);printf("%d\n",query(l,r));}}return 0;
}

 

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

---