【每日一题】4月21日题目精讲 枚举

题号 NC14583
名称 糖糖别胡说，我真的不是签到题目
来源 北京理工大学珠海学院第七届C语言程序设计竞赛
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

任何问题都有一个从简单到复杂的过程——先考虑没有娇姐发功怎么做：
我们可以考虑每只糖糖最后能不能存活：第i只糖糖能存活的条件是他后面没有比他大的另外一组的糖糖，所以我们只需要从后往前扫描维护当前位置往后每一组糖糖的最大值是多少然后和当前糖糖的能力值比较就行。
现在再来考虑娇姐发功的问题：
娇姐会在第ci秒使得前ci个人的能力值+1，其实不影响第ci个糖糖在第ci秒消灭他前面的糖糖——大家都加一，大小关系不变；但是会影响后面的糖糖打他。换句话说，第x个糖糖开始能打前面的糖糖的时候看到的前面的糖糖数字是第x秒的数字，而随着之后大家一起增大，大小关系就不变了，所以用每个人最后他的能力值判断能不能存活就行了。
于是我们只需要把先得出每个糖糖最后的能力值，再从后往前判断他是否还存活。维护每个糖糖最后的能力值可以用差分来维护，也可也累加一下当前位置x即x往后贡献了多少个加一就可以了。

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月28日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴