RainAir
My OI Blog
RainAir
HDU 5306 Gorgeous Sequence

题目链接

题目描述

(本人喜欢用 Vjudge 所以就放那里的链接啦。
给定一个序列,要求实现区间求最大值,区间求和,区间对一个数取min。

解题报告

开始挖十一集训的坟了……
这一题是吉司机线段树模板题的简化版本。
大家都会维护最大值和和,怎么实现那个取min的操作呢?
我们考虑对于每个区间都先维护出这个区间的最大值 max,次大值 se,最大值出现的次数 cnt。
这样在覆盖的时候分类讨论一下,设这个区间要对x整体取min:
如果当前区间 $max \leq x$ 就不用继续处理了因为这个区间不会改变;
如果当前区间 $ max \geq x $ 并且 $se \leq x $ 那么只需要将这个区间的最大值改一下就可以了。
否则就递归左右子树继续找,最后合并一下就可以了。
合并也是要分类讨论的 $qwq$.
合并注意下要判断两边的max相等的情况,这时候的cnt和se取值都与一般情况不同。
还有一个小问题:我不知道为什么我如果去掉注释里的CLR函数(即memset) 就会提示我MLE?我十分的疑惑,如果有知道的神犇请在评论里告诉我 $qwq$ 谢谢。
另外这个题目还有一个 进阶版本,按照这种分类讨论操作的思想写就可以了,只不过可能代码量会 长一些。

代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/270
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

HDU 5306 Gorgeous Sequence
题目链接 题目描述 (本人喜欢用 Vjudge 所以就放那里的链接啦。 给定一个序列,要求实现区间求最大值,区间求和,区间对一个数取min。 解题报告 开始挖十一集训的坟了...... 这一题…
扫描二维码继续阅读
2018-11-18
标签
近期评论