热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

CF739CAlyonaandtowers解题报告

线段树绝世好题。题意:维护区间加,全局最长单峰序列。Solution:维护\(8\)个量。\(lval\):左端点的权值。\(rval\):右端点的权值。\(lmax\):以左端点

线段树绝世好题。


题意:

维护区间加,全局最长单峰序列。


Solution:

维护 \(8\) 个量。

\(lval\):左端点的权值。

\(rval\):右端点的权值。

\(lmax\):以左端点开始的最长的下降序列长度。

\(rmax\):以右端点结束的最长的上升序列长度。

\(lans\):以左端点开始的最长的单峰序列长度。

\(rans\):以右端点结束的最长的单峰序列长度。

\(ans\): 区间内最长的单峰序列长度。

\(tag\):区间加法懒标记。

考虑怎么用左右两个儿子更新父节点的信息。

\(lson\) 来表示左儿子,\(rson\) 来表示右儿子,\(rt\) 来表示父节点。


\(lval\)

显然父节点的 \(lval\) 是左儿子的 \(lval\)


\(rval\)

显然父节点的 \(rval\) 是右儿子的 \(rval\)


\(lmax\)

如果说左儿子的 \(lmax\) 等于左儿子的区间长度,说明了左区间是个下降区间,如果同时左儿子的 \(rval\) 大于了右儿子的 \(lval\) 说明了父节点的 \(lmax\) 能向右区间伸展,这个时候 \(rt.lmax = lson.lmax + rson.lmax\)

否则无法跨过右区间,直接继承左儿子的值:\(rt.lmax = lson.lmax\)


\(rmax\)

如果说右儿子的 \(rmax\) 等于右儿子的区间长度,说明了右区间是个上升区间,如果同时左儿子的 \(rval\) 小于了右儿子的 \(lval\) 说明了父节点的 \(rmax\) 能向左区间伸展,这个时候 \(rt.rmax = lson.rmax + rson.rmax\)

否则无法跨过左区间,直接继承右儿子的值: \(rt.rmax = rson.rmax\)


\(lans\)

如果说左儿子的 \(rmax\) 等于左儿子的区间长度,说明了左儿子是个上升区间。

这个时候分两种情况:



  • \(lson.rval 说明了还能通过右儿子的 \(lans\) 继续扩展:\(rt.lans = lson.rmax + rson.lans\)

-\(lson.rval > rson.lval\) 说明了只能通过右儿子的 \(lmax\) 继续扩展: \(rt.lans = lson.rmax + rson.lmax\)

如果说左儿子的 \(lans\) 等于区间长度,想用右儿子扩展的话,必须满足 \(lson.rval > rson.lval\),这个时候:\(rt.lans = lson.lans + rson.lmax\)

否则无法通过右区间来更新,直接继承左儿子的值:\(rt.lans = lson.lans\)


\(rans\)

如果说右儿子的 \(lmax\) 等于右儿子的区间长度,说明了右儿子是个下降区间。

这个时候分两种情况:



  • \(lson.rval > rson.lval\) 说明了还能通过左儿子的 \(rans\) 继续扩展:\(rt.rans = lson.rans + rson.lmax\)



  • \(lson.rval 说明了只能通过左儿子的 \(rmax\) 继续扩展: \(rt.rans = lson.rmax + rson.lmax\)



如果说右儿子的 \(lans\) 等于区间长度,想用左儿子扩展的话,必须满足 \(lson.rval ,这个时候:\(rt.rans = lson.rmax + rson.lans\)

否则无法通过右区间来更新,直接继承左儿子的值:\(rt.rans = rson.rans\)



推荐阅读
  • 提升Python编程效率的十点建议
    本文介绍了提升Python编程效率的十点建议,包括不使用分号、选择合适的代码编辑器、遵循Python代码规范等。这些建议可以帮助开发者节省时间,提高编程效率。同时,还提供了相关参考链接供读者深入学习。 ... [详细]
  • Monkey《大话移动——Android与iOS应用测试指南》的预购信息发布啦!
    Monkey《大话移动——Android与iOS应用测试指南》的预购信息已经发布,可以在京东和当当网进行预购。感谢几位大牛给出的书评,并呼吁大家的支持。明天京东的链接也将发布。 ... [详细]
  • 本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值,函数可以作为变量自由传递,也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性,为程序开发带来了便利。 ... [详细]
  • GetWindowLong函数
    今天在看一个代码里头写了GetWindowLong(hwnd,0),我当时就有点费解,靠,上网搜索函数原型说明,死活找不到第 ... [详细]
  • 本文分享了一个关于在C#中使用异步代码的问题,作者在控制台中运行时代码正常工作,但在Windows窗体中却无法正常工作。作者尝试搜索局域网上的主机,但在窗体中计数器没有减少。文章提供了相关的代码和解决思路。 ... [详细]
  • PHP设置MySQL字符集的方法及使用mysqli_set_charset函数
    本文介绍了PHP设置MySQL字符集的方法,详细介绍了使用mysqli_set_charset函数来规定与数据库服务器进行数据传送时要使用的字符集。通过示例代码演示了如何设置默认客户端字符集。 ... [详细]
  • Java序列化对象传给PHP的方法及原理解析
    本文介绍了Java序列化对象传给PHP的方法及原理,包括Java对象传递的方式、序列化的方式、PHP中的序列化用法介绍、Java是否能反序列化PHP的数据、Java序列化的原理以及解决Java序列化中的问题。同时还解释了序列化的概念和作用,以及代码执行序列化所需要的权限。最后指出,序列化会将对象实例的所有字段都进行序列化,使得数据能够被表示为实例的序列化数据,但只有能够解释该格式的代码才能够确定数据的内容。 ... [详细]
  • Android中高级面试必知必会,积累总结
    本文介绍了Android中高级面试的必知必会内容,并总结了相关经验。文章指出,如今的Android市场对开发人员的要求更高,需要更专业的人才。同时,文章还给出了针对Android岗位的职责和要求,并提供了简历突出的建议。 ... [详细]
  • 本文介绍了如何使用php限制数据库插入的条数并显示每次插入数据库之间的数据数目,以及避免重复提交的方法。同时还介绍了如何限制某一个数据库用户的并发连接数,以及设置数据库的连接数和连接超时时间的方法。最后提供了一些关于浏览器在线用户数和数据库连接数量比例的参考值。 ... [详细]
  • 本文比较了eBPF和WebAssembly作为云原生VM的特点和应用领域。eBPF作为运行在Linux内核中的轻量级代码执行沙箱,适用于网络或安全相关的任务;而WebAssembly作为图灵完备的语言,在商业应用中具有优势。同时,介绍了WebAssembly在Linux内核中运行的尝试以及基于LLVM的云原生WebAssembly编译器WasmEdge Runtime的案例,展示了WebAssembly作为原生应用程序的潜力。 ... [详细]
  • 本文介绍了在Python3中如何使用选择文件对话框的格式打开和保存图片的方法。通过使用tkinter库中的filedialog模块的asksaveasfilename和askopenfilename函数,可以方便地选择要打开或保存的图片文件,并进行相关操作。具体的代码示例和操作步骤也被提供。 ... [详细]
  • PHP图片截取方法及应用实例
    本文介绍了使用PHP动态切割JPEG图片的方法,并提供了应用实例,包括截取视频图、提取文章内容中的图片地址、裁切图片等问题。详细介绍了相关的PHP函数和参数的使用,以及图片切割的具体步骤。同时,还提供了一些注意事项和优化建议。通过本文的学习,读者可以掌握PHP图片截取的技巧,实现自己的需求。 ... [详细]
  • 本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • 开发笔记:加密&json&StringIO模块&BytesIO模块
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了加密&json&StringIO模块&BytesIO模块相关的知识,希望对你有一定的参考价值。一、加密加密 ... [详细]
  • 如何使用Java获取服务器硬件信息和磁盘负载率
    本文介绍了使用Java编程语言获取服务器硬件信息和磁盘负载率的方法。首先在远程服务器上搭建一个支持服务端语言的HTTP服务,并获取服务器的磁盘信息,并将结果输出。然后在本地使用JS编写一个AJAX脚本,远程请求服务端的程序,得到结果并展示给用户。其中还介绍了如何提取硬盘序列号的方法。 ... [详细]
author-avatar
潘月飞--_758
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有