`

杭电 hdu 1754 I Hate It (线段树 + 详细注释)

阅读更多
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1754
    Name  : 1754 I Hate It

    Date  : Wednesday, September 14, 2011
    Time Stage : half an hour and one hour

    Result: 
4602821	2011-09-14 22:09:08	Accepted	1754
484MS	7160K	2609 B
C++	pyy

4602802	2011-09-14 22:07:05	Output Limit Exceeded	1754
125MS	7136K	2660 B
C++	pyy

4602785	2011-09-14 22:05:30	Time Limit Exceeded	1754
3000MS	7132K	2646 B
C++	pyy

4602584	2011-09-14 21:45:47	Time Limit Exceeded	1754
3000MS	7132K	2525 B
C++	pyy

4602563	2011-09-14 21:43:53	Time Limit Exceeded	1754
3000MS	7132K	2531 B
C++	pyy

4602534	2011-09-14 21:40:48	Time Limit Exceeded	1754
3000MS	7132K	2531 B
C++	pyy


Test Data :

Review :
一开始超时超得莫名其妙,艰苦调试之,发现一个很诡异的现象,就是
Update() 竟然会自动执行多一次!
一开始update() 函数的倒数第二句是这样写的:
tree[root].max = max (update (2 * root, pos, val), update (2 * root + 1, pos, val)) ;

于是为了观察其内部究竟是为何会多执行一次,别将其分立开来:
	int a, b ;
	a = update (2 * root, pos, val) ;
	b =	update (2 * root + 1, pos, val) ;

	tree[root].max = max (a, b) ;
发现它竟然又正常了!正在纳闷之际,猛然看到了max()函数的定义,竟然是宏定义:
#define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))
于是一切豁然开朗,因为宏定义在展开的时候会这样:
max (update (2 * root, pos, val), update (2 * root + 1, pos, val)) ;
等同于:
((update (2 * root, pos, val)) > (update (2 * root, pos, val)) ? (update (2 * root, pos, val)) : (update (2 * root, pos, val)))
于是乎每次遇到max()展开之后就会出现四个update()函数,相当于多了指数级的执行次数!
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <conio.h>
#include <string.h>

#define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))
#define min(x1, y1) ((x1) < (y1) ? (x1) : (y1))

#define MAXSIZE 200002

typedef struct {
	int max ;
	int left, right ;
} NODE ;

int		n, m ;
int		num [MAXSIZE] ;
NODE	tree[MAXSIZE * 20] ;

// 构建线段树
int build (int root, int left, int right)
{
	int mid ;

	// 当前节点所表示的区间
	tree[root].left		= left ;
	tree[root].right	= right ;

	// 左右区间相同,则此节点为叶子,max 应储存对应某个学生的值
	if (left == right)
	{
		return tree[root].max = num[left] ;
	}
	mid = (left + right) / 2 ;

	// 递归建立左右子树,并从子树中获得最大值
	int a, b ;
	a = build (2 * root, left, mid) ;
	b = build (2 * root + 1, mid + 1, right) ;

	return tree[root].max = max (a, b) ;
}

// 从节点 root 开始,查找 left 和 right 之间的最大值
int find (int root, int left, int right)
{
	int mid ;
	// 若此区间与 root 所管理的区间无交集
	if (tree[root].left > right || tree[root].right < left)
		return 0 ;
	// 若此区间包含 root 所管理的区间
	if (left <= tree[root].left && tree[root].right <= right)
		return tree[root].max ;

	// 若此区间与 root 所管理的区间部分相交

	int a, b ;	// 不能这样 max (find(...), find(...));
	a = find (2 * root, left, right) ;
	b = find (2 * root + 1, left, right) ;

	return max (a, b) ;
}

// 更新 pos 点的值
int update (int root, int pos, int val)
{
	// 若 pos 不存在于 root 所管理的区间内
	if (pos < tree[root].left || tree[root].right < pos)
		return tree[root].max ;

	// 若 root 正好是一个符合条件的叶子
	if (tree[root].left == pos && tree[root].right == pos)
		return tree[root].max = val ;

	// 否则。。。。

	int a, b ;	// 不能这样 max (find(...), find(...));
	a = update (2 * root, pos, val) ;
	b =	update (2 * root + 1, pos, val) ;

	tree[root].max = max (a, b) ;

	return tree[root].max ;
}

int main ()
{
	char c ;
	int i ;
	int x, y ;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		for (i = 1 ; i <= n ; ++i)
			scanf ("%d", &num[i]) ;
		build (1, 1, n) ;

		for (i = 1 ; i <= m ; ++i)
		{
			getchar () ;
			scanf ("%c%d%d", &c, &x, &y) ;
			if (c == 'Q')
			{
				printf ("%d\n", find (1, x, y)) ;
			}
			else
			{
				num[x] = y ;
				update (1, x, y) ;
			}
		}
	}
	return 0 ;
}

1
0
分享到:
评论
2 楼 panyanyany 2011-09-17  
基德KID.1412 写道
Y神牛啊!!!顶顶顶,哈哈!

都是受华神渲染的结果啊!!
1 楼 基德KID.1412 2011-09-16  
Y神牛啊!!!顶顶顶,哈哈!

相关推荐

    电动车上牌管理系统 SSM毕业设计 附带论文.zip

    电动车上牌管理系统 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B

    tornado-6.1-cp39-cp39-manylinux2010_x86_64.whl

    tornado-6.1-cp39-cp39-manylinux2010_x86_64.whl

    【eclipse和idea两个版本运行源码】基于Java Swing +mysql 实现的网吧管理系统

    一、项目简介 本项目是一套基于Java Swing 开发的网吧管理系统,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,确保可以运行! 该系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用价值。 二、技术实现 ​后台技术:java swing ​数据库:MySQL ​数据库连接池:c3p0 三、系统主要功能 用户登录: 分为 普通用户和管理员 两种角色 菜单模块:上机,下机, 系统设置:管理员设置,会员设置,计费设置, 退出系统 管理模块:增加会员,删除会员,信息修改,信息查询 视图模块:主页视图,在线用户,统计视图, 统计报表模块:人数报表,收入报表 帮助模块:联系我们,关于系统 详见:https://blog.csdn.net/weixin_43860634/article/details/125247764

    pc-dmis软件脚本-输出Excel格式报告

    使用软件自带的basic脚本编辑制作的脚本 低版本软件无法输出Excel报告,可以通过脚本方式实现这一功能

    【java毕业设计】校园失物招领系统源码(springboot+vue+mysql+说明文档).zip

    项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse

    基于java的网上电子书店h答辩PPT.pptx

    基于java的网上电子书店h答辩PPT.pptx

    基于微信小程序的微信小程序校园失物招领答辩PPT.pptx

    基于微信小程序的微信小程序校园失物招领答辩PPT.pptx

    基于java的基于Java的学生综合测评管理系统答辩PPT.pptx

    基于java的基于Java的学生综合测评管理系统答辩PPT.pptx

    pandas-2.1.4-cp39-cp39-win_amd64.zip

    pandas whl安装包,对应各个python版本和系统(具体看资源名字),找准自己对应的下载即可! 下载后解压出来是已.whl为后缀的安装包,进入终端,直接pip install pandas-xxx.whl即可,非常方便。 再也不用担心pip联网下载网络超时,各种安装不成功的问题。

    判断题 - 题目列表 - 图-练习题集飒飒阿萨

    springboot体育器材管理系统(附源码+数据库)71175

    管理员功能: 用户管理:管理员可以管理用户账户,包括审核新注册用户、禁用违规用户、重置密码等操作。 器材管理:管理员可以管理器材的信息,包括添加新器材、编辑器材详情、设定器材规则和限制等。 器材预约与借还管理:管理员可以处理用户的器材预约请求,确认或调整预约时间,并记录借还操作。 库存管理:管理员可以监控器材库存情况,及时补充不足的器材并处理损坏或报废的器材。 数据统计与报表:管理员可以分析系统的使用情况和借还记录,生成数据统计报表以了解器材使用情况和借还频率等。 系统设置与维护:管理员可以进行系统设置,包括配置器材规则、设定可用时间段、备份数据、优化系统性能等。 消息通知与提醒:管理员可以向用户发送消息通知,如器材预约成功、归还提醒、系统更新通知等。

    Jira插件安装包Dynamic-forms

    Jira插件安装包Dynamic-forms

    pandas-2.1.4-cp311-cp311-win_amd64.zip

    pandas whl安装包,对应各个python版本和系统(具体看资源名字),找准自己对应的下载即可! 下载后解压出来是已.whl为后缀的安装包,进入终端,直接pip install pandas-xxx.whl即可,非常方便。 再也不用担心pip联网下载网络超时,各种安装不成功的问题。

    少儿图形化scratch编程作品源码集100个

    Scratch是一款由麻省理工学院(MIT)的“终身幼儿园团队”开发的图形化编程工具,专为儿童设计,旨在帮助他们学习编程思维和逻辑能力。

    基于java的学生就业管理系统答辩PPT.pptx

    基于java的学生就业管理系统答辩PPT.pptx

    课设毕设基于SpringBoot+Vue的旅游门票信息系统设计与实现源码可运行.zip

    本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac

    大学志愿填报系统.zip

    随着社会对志愿服务活动的日益重视,各大高校也纷纷参与到志愿服务的行列中。为了更好地管理和记录志愿者活动,提高志愿服务的质量和效率,我们开发了这款大学志愿服务系统。 该系统主要包括多个功能模块,如信息管理、活动管理、学生管理等。信息管理模块允许学校管理员录入、修改和删除学校的基本信息,包括学校账号、名称、联系电话、地址、特色以及办学理念等,确保信息的准确性和完整性。活动管理模块则用于记录和管理志愿者活动的相关信息,包括活动的名称、时间、地点、参与人员等,方便志愿者进行报名和签到。 此外,系统还提供了学生管理模块,用于记录学生的志愿服务经历和表现,为学生参与志愿服务提供便利。同时,系统还支持照片上传和展示功能,通过展示志愿者活动的照片,让更多人了解和关注志愿服务事业。 整个系统界面简洁明了,操作便捷,功能强大。通过使用该系统,高校可以更加高效地管理和记录志愿者活动,提高志愿服务的整体水平。同时,该系统也为广大志愿者提供了一个展示自我、服务社会的平台。

    turbo均衡算法研究

    turbo均衡算法研究

    静态编译的Qt6.7.3(win10+MSVC2022+openssl+静态运行时) part01

    https://blog.csdn.net/aggs1990/article/details/143491823 静态编译的Qt6.7.3(win10+MSVC2022+openssl+静态运行时) 压缩包比较大,这是第一部分

    tornado-6.4b1-cp38-abi3-musllinux_1_1_i686.whl

    tornado-6.4b1-cp38-abi3-musllinux_1_1_i686.whl

Global site tag (gtag.js) - Google Analytics