`
kenby
  • 浏览: 723793 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

poj 2823 线段树

 
阅读更多

赤裸裸的线段树,数据量很大,加了IO优化函数。

 

#include <stdio.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b)

#define inf 20000000
#define N 1000001

struct tree_node
{
	int min, max;
};

struct tree_node tree[2097152];
int 	n, M;
int 	max[N], min[N];

/* IO优化 */
inline void put(int x){
	static char 	s[20];
	int				bas;

	if(x< 0) {
		putchar('-');
		x = -x;
	}
	if(x == 0) {
		putchar('0');
		return;
	}
	bas = 0;
	for(;x;x/=10) s[bas++] = x%10+'0';
	for(;bas--;) putchar(s[bas]);
}

inline void build_tree()
{
	int		i;

	//不用的叶子节点
	for (i = n+1; i%M != 1; i++) {
		tree[(i%M)+M].min = inf;
		tree[(i%M)+M].max = -inf;
	}
	//分支节点
	for (i = M-1; i > 0 ; i--) {
		tree[i].min = MIN(tree[i<<1].min, tree[(i<<1)+1].min);
		tree[i].max = MAX(tree[i<<1].max, tree[(i<<1)+1].max);
	}
}

inline void query(int s, int t)
{
	int 	i;

	i = s;
	max[i] = -inf;
	min[i] = inf;

	for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
		if (~s&1) {
			max[i] = MAX(max[i], tree[s^1].max);
			min[i] = MIN(min[i], tree[s^1].min);
		}
		if (t&1) {
			max[i] = MAX(max[i], tree[t^1].max);
			min[i] = MIN(min[i], tree[t^1].min);
		}
	}
}

int main()
{
	int		i, k;

	scanf("%d %d", &n, &k);
	for (M = 1; M < (n+2); M <<= 1);
	for (i = M+1; i <= n+M; i++) {
		scanf("%d", &tree[i].min);
		tree[i].max = tree[i].min;
	}

	build_tree();

	for (i = 1; i <= (n-k+1); i++) {
		query(i, i+k-1);
	}
	put(min[1]);
	for (i = 2; i <= (n-k+1); i++) {
		putchar(' ');
		put(min[i]);
	}
	putchar('\n');
	put(max[1]);
	for (i = 2; i <= (n-k+1); i++) {
		putchar(' ');
		put(max[i]);
	}
	putchar('\n');
	return 0;
}
分享到:
评论

相关推荐

    poj2823.cpp.tar.gz_线段树

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

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

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

    线段树练习POJ 3264

    线段树是一种数据结构,常用于处理区间查询与更新的问题,它能高效地支持动态维护区间最值、求和等问题。在本题“POJ 3264”中,我们可能面临的是一个区间最值或者区间求和的计算任务。线段树的基本思想是将数组或...

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

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

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

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

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

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

    POJ 部分题解 解题报告

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

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

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

    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

    线段树题目

    - **ZOJ 1610** 和 **POJ 2777**:这两道题都是典型的线段覆盖问题,需要利用线段树来解决。基本思路是通过线段树维护每个区间是否被覆盖的状态。对于每个覆盖请求,更新线段树对应区间中的覆盖状态,并统计完全被...

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

    ### ACM数据结构之树状数组和线段树 #### 线段树 线段树是一种非常有效的数据结构,主要用于解决区间查询问题。它能够快速地处理区间内的各种操作,如查询、修改等。 ##### 线段树的定义与特性 线段树本质上是一...

    poj 2763 housewife Wind

    poj 2763 程序 线段树 LCA 2000MS AC

    POJ2777 个人代码

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

    pku1151.rar_Atlantis_pku 11_poj Atlant_poj Atlantis_poj11

    描述中提到的“POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。”揭示了问题的核心内容。这是一个涉及到线段树数据结构的编程问题,目标是计算某个区域的面积,可能是在二维平面上。线段树是一种高效...

    poj训练计划.doc

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

    poj题目分类

    * 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态二叉检索树:例如 poj2482、poj2352。 * 树状树组:例如 poj1195、poj3321。 * RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 ...

    poj各种分类

    在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...

    acm poj300题分层训练

    poj2528、poj2777等是线段树的题目,poj2482、poj2352等涉及平衡树,poj1195、poj3321则训练了树状数组。 5. **搜索算法的优化**:poj1699、poj3411等训练搜索技巧和剪枝方法,poj3373、poj1691则介绍了记忆化搜索。...

    史上最全poj题目分类

    线段树是一种常用的数据结构,线段树的核心思想是将数据存储在一个树形结构中,然后通过树的遍历进行搜索。例如,在搜索中,线段树可以用于快速地搜索数据。 树状数组是一种常用的数据结构,树状数组的核心思想是将...

Global site tag (gtag.js) - Google Analytics