`

poj 3264 Balanced Lineup (线段树)

阅读更多

题目链接

 

解题报告:线段树的入门题目,这里只需要两种操作“建树”、“查询”。

 

线段树解题的关键是节点存放的信息

 

#include <cstdio>
#include<cstring>
#include<algorithm>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b 
#define mid(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) a<<1|1

const int MAX = 200000+10;
const int INF = 0x3fffffff;

int h[MAX],mini,maxn;

struct node
{
	int l,r;
	int min,max;
};
node a[MAX];

void build(int t,int l,int r)
{
	a[t].l=l;
	a[t].r=r;//当初这忘记了记录 
	if( l != r )
	{
		int m=mid(l,r);
		build(L(t),l,m);//应该是L而不是数字1; 
		build(R(t),m+1,r);
		a[t].min=min(a[L(t)].min,a[R(t)].min);
		a[t].max=max(a[L(t)].max,a[R(t)].max);
	}
	else
	{
		a[t].min=h[l];
		a[t].max=h[l];
	}
}

void query(int t,int l,int r)
{
	if(a[t].min >= mini && a[t].max <= maxn)
		return ;
	int m=mid(a[t].l,a[t].r);
	if(a[t].l==l&&a[t].r==r)
	{
		mini=min(mini,a[t].min);
		maxn=max(maxn,a[t].max);	
	}
	else if(l>m)//注意L表示的是什么 
	{
		query(R(t),l,r);
	}
	else if(r<=m)
	{
		query(L(t),l,r);
	}
	else
	{
		query(R(t),m+1,r);
		query(L(t),l,m);		
	}
}

int main()
{
	int n,q,l,r;
	while(scanf("%d%d",&n,&q)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&h[i]);
		build(1,1,n);
		for(int i=0;i<q;i++)
		{
			maxn=-INF;
			mini=INF;
			scanf("%d %d",&l,&r);
			query(1,l,r);
			printf("%d\n",maxn-mini);
		} 
	}
	return 0;
}

 

0
6
分享到:
评论

相关推荐

    线段树练习POJ 3264

    题目中给出的`Main3264.java`文件很可能是实现线段树并解决具体问题的代码。为了更好地理解这个程序,我们需要查看源码,分析其中的类、方法以及它们如何协同工作以满足题目需求。通常,线段树的类会包含构造函数、...

    POJ3274-Gold Balanced Lineup

    【标题】"POJ3274-Gold Balanced Lineup" 是一道来自北京大学在线判题系统POJ(Problem Online Judge)的编程竞赛题目。这道题目的主要目标是通过编写程序来解决一个与数学和算法相关的问题。 【描述】"北大POJ3274...

    线段树入门学习(二)(兼解POJ3468) JAVA

    在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    线段树入门学习(三)懒操作(兼解POJ1823) JAVA

    在本篇博文中,我们将深入探讨线段树的概念,以及如何实现懒惰更新(Lazy Propagation)策略,同时结合POJ1823问题进行实战应用。懒惰更新是优化线段树性能的关键技巧,它避免了频繁地对每个节点进行更新,从而减少...

    poj2823.cpp.tar.gz_线段树

    在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...

    poj 2352 stars(树状数组,线段树)

    ### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...

    POJ2528-Mayor's posters【区间映射压缩(离散化)+线段树】

    POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========&gt; 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573

    POJ2777 个人代码

    POJ题解 个人写法 线段树每个人都不一样

    ACM数据结构之树状数组和线段树

    以题目 POJ3264 BalancedLineup 为例,该题目要求多次求任一区间 Ai–Aj 中最大数和最小数的差。使用线段树来解决这个问题是非常合适的。 1. **树节点结构设计**:每个节点除了保存区间起点和终点之外,还需要保存...

    线段树题目

    - **POJ 3264**:简单的线段树题目,需要求解区间内的最大值和最小值。这种问题通常只需要在线段树的节点中维护最大值和最小值即可。 - **POJ 1151**:结合了线段树和离散化的技巧来求解矩形面积的并集。这需要对...

    poj 1989 The Cow Lineup.md

    poj 1989 The Cow Lineup.md

    POJ 部分题解 解题报告

    10. **POJ 2528 线段树.txt**:这是第三个线段树相关的题目,解题报告可能会深入讲解线段树在不同场景下的应用。 通过阅读这些解题报告,你可以学习到各种高级算法的应用,如动态规划、搜索算法、数据结构(如线段...

    POJ 1751 求最小生成树prim算法(JAVA)

    标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...

    poj 2763 housewife Wind

    poj 2763 程序 线段树 LCA 2000MS AC

    poj题目分类

    * RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 poj1703、poj2492。 * KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 *...

    ACM中的RMQ和LCA问题

    POJ 3264 Balanced Lineup和POJ 2823 Sliding Window问题则分别展示了RMQ问题在不同场景下的应用。 总的来说,RMQ和LCA是ACM中重要且实用的数据结构问题,它们涉及到动态规划、线段树、Sparse Table、并查集等多种...

    二维树状数组学习之二:练习POJ 1195

    在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...

    poj训练计划.doc

    - RMQ(区间查询):如`poj3264, poj3368`。 - 并查集的高级应用:如`poj1703, poj2492`。 - **搜索** - 最优化剪枝和可行性剪枝:如`poj3411, poj1724`。 - **动态规划** - 复杂的动态规划:如`poj1191, poj...

Global site tag (gtag.js) - Google Analytics