「JOISC 2022 Day4」鱼 2

本文主要是介绍「JOISC 2022 Day4」鱼 2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考虑怎么样的鱼能取得最后的胜利，它一定是不断贪心地往两边吃，能吃就吃。

实现以上过程的一个朴素想法是，对左右两边分别维护”有效“单调栈，暴力扫一遍。

考虑用线段树维护上述过程，思考如何合并区间信息。

假设有 \(x\) 条鱼能在左子树中吃完所有的鱼，那么加入右区间后，它们的增广方向一定是单向的。

这时候发现需要分别维护区间从左和从右开始的“有效”单调栈，也就是维护从左端点或右端点开始吃，在哪些点会停下的栈。

那么就可以快速判断能吃光原区间的鱼能否在新区间依然取得成功。

可以发现栈大小最多为 \(\log_2V\) 个，因为每次跨过障碍后数值至少乘 \(2\)。

还有一种情况是在原区间并不能成功，但是在新区间时通过吃掉另一个区间的一些鱼而取得成功。

首先如果它吃不到另一个区间那么它就永远不可能吃掉全部。

那么只需考虑能吃掉一段前缀或是后缀的位置，把这些都记在它们第一个不能吃到的位置上。可以发现这些位置都在“有效”单调栈上。

接着考虑如何判断能否成为答案。

可以发现能成功的点构成一个前/后缀，那么一个朴素的想法是二分这个位置暴力判断，时间复杂度为 \(\mathcal O(N\log_2 N\log_2V\log\log_2V)\)。

进一步分析可以发现，从小到大枚举若失败则从断点开始继续走，这样合并区间信息的复杂度就是 \(\mathcal O(\log_2V)\)。

总时间复杂度为 \(\mathcal O(N\log_2V\log_2N)\)

这篇关于「JOISC 2022 Day4」鱼 2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！