频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 3264 Balanced Lineup(RMQ线段树)
2014-02-13 15:25:13      个评论    来源:poj 3264 Balanced Lineup(RMQ线段树)  
收藏   我要投稿

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

题意:输入n个数,有m个询问,每个询问输入l,r,求区间[ l , r ]之间最大数与最小数之差。

思路:

我用的线段树过的,节点增加两个域,分别记录该区间的最大值和最小值。然后设置全局变量maxh和minh动态维护区间[ l, r]中的最大值和最小值。

不过线段树过时间不是一般的慢,3s+。。。


#include 
#include 
#include 

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 50005;

struct line
{
	int l;
	int r;
	int minh;
	int maxh;
}tree[maxn<<2];

int a[maxn];
int maxh;
int minh;

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	if(l == r)
	{
		tree[v].maxh = a[l];
		tree[v].minh = a[l];
		return;
	}
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
	tree[v].maxh = max(tree[v*2].maxh,tree[v*2+1].maxh);
	tree[v].minh = min(tree[v*2].minh,tree[v*2+1].minh);
}

void query(int v, int l, int r)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		maxh = max(maxh,tree[v].maxh);	//maxh,minh动态维护
		minh = min(minh,tree[v].minh);
		return;
	}
	int mid = (tree[v].l+tree[v].r)>>1;
	if(r <= mid)
		 query(v*2,l,r);
	else
	{
		if(l > mid)
			query(v*2+1,l,r);

		else
		{
			query(v*2,l,mid);
			query(v*2+1,mid+1,r);

		}
	}
}

int main()
{
	int n,m;

	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	build(1,1,n);

	int l,r;
	while(m--)
	{
		scanf("%d %d",&l,&r);
		maxh = 0;
		minh = INF;	//不要忘记初始化
		query(1,l,r);
		printf("%d\n",maxh-minh);
	}
	return 0;
}





点击复制链接 与好友分享!回本站首页
相关TAG标签 线段
上一篇:LeetCode----Max Points On a Line
下一篇:uva - 10881 - Piotr's Ants(等效变换,排序)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站