U477940 大鱼吃小鱼 题解

CommonAnts · 2025-02-06 21:22:17 · 题解

题目中 \{a_i\} 表示鱼的体型，n 表示总数。

首先，任何时候鱼的状态一定是吃完了一个区间位置中的所有鱼。并且鱼的体型一定等于区间内鱼的初始体型之和。所以我们用这个区间来表示鱼的状态。以下，将区间内的鱼的体型之和简称为区间和。

我们称：

• 一个无法不用道具扩展的区间是自闭区间。（我们规定 [1,n] 也是）
• 区间和 \ge k 的区间是大鱼区间。
• 区间和 \lt k 的区间是小鱼区间。

显然，小鱼区间是不可能不用道具去吃任何鱼的（因为鱼的体型都非负）。

我们考虑任何一个鱼从初始吃完所有鱼的过程。这个过程中鱼的体型显然是单调不降的，存在一个时刻第一次变成大鱼，在这之前必然每一步吃鱼都要用道具。（或者可能整个序列都是小鱼，这种情况下答案为 n-1。这种情况要特判。）我们从这个时刻把一个方案分成前后两段：

• 从最开始到第一个大鱼区间：使用道具次数是大鱼区间的长度减 1。容易证明这第一个大鱼区间一定是序列上固定某个左端点或者右端点前提下的极短大鱼区间，不超过 2n 种。因此只要双指针预处理出这些极短大鱼区间，想办法求出每个极短大鱼区间在后半段的最小道具数，再用单调队列更新每个 i 的答案即可。
• 从第一个大鱼区间到整个序列。剩下的问题是求出每个极短大鱼区间在后半段的最小道具数。

如果两个自闭区间相交但互不包含，可以证明它们的交集部分一定是小鱼区间。（否则，我们设它们按位置顺序是 A-b-C-d-E，其中 b,d 是单条鱼，A,E 可以为空，C 不为空，两个自闭区间分别是 A-b-C 和 C-d-E。则，按自闭的定义有 d \gt A+b+C-k, b\gt C+d+E-k。如果 C \ge k 就有 d\gt A+b \ge b \gt d+E \ge d，矛盾。）

另外，容易证明一个自闭的大鱼区间下一步用道具吃的一定是两侧相邻的鱼中体型较大的，因为吃了较大的那个后体型一定足够立刻吃较小的，这总是更优。

所以对于一个大鱼区间，所有包含它的自闭区间必然组成区间套，并且方案选择是固定的。

另外，这也容易证明大鱼自闭区间的总数不超过 2n 个。我们考虑把一个大鱼自闭区间关联到它两侧相邻的鱼中较小的那个上，容易证明每个鱼在每一侧最多会被一个大鱼自闭区间关联。（设它们按位置顺序是 a-B-c-D，容易证明不可能有 B 和 B-c-D 都是大鱼自闭区间且有 a\le c。否则 B+c+D\ge B+a+D \gt B+(B+c+D-k)+D \ge B+(k+c+D-k)+D = B+c+2D，矛盾）

现在问题有两个：

1. 如何求出所有的大鱼自闭区间。
2. 如何求出每个大鱼自闭区间扩展到全序列的最小操作次数（以下简称扩展到全序列的最小操作次数为“答案”）。

对于第一个问题，我们考虑分别对于每个位置求出每一侧与他相关联的那个大鱼自闭区间（若存在）。我们考虑从左往右枚举 i，并用双指针维护以 i-1 为右端点的极短大鱼区间记为 [L_{i-1},i-1]，并在 i 增加过程中维护 L_{i-1}-1 左侧所有的点集 S 中可能成为左相邻点的，试图求出以 i-1 为右端点且关联到 i 的大鱼自闭区间。那么：

• 在 S 中，一个下标、体型都小的位置必然从当前 i 开始都永远不可能是（大鱼自闭区间的）左相邻点。所以我们首先用单调栈维护 S，只保留那些体型后缀最大的位置。
• 在 S 中，每次我们要查询 \ge a_i 的最小鱼并判断，只有这条鱼和 i 有可能构成大鱼自闭区间。但是我们可以注意到，S 中那些 \le a_i 的鱼对于更大的 i 也不可能是大鱼自闭区间的左相邻点（因为 \sum a_{[L_{i-1},i-1]}+a_i \ge k+a_i 就已经足够吃它了），所以我们这个查询直接在单调栈上删除元素即可。（注意有一种边界细节是，大鱼自闭区间是整个序列的前缀或后缀，S 删空了。）

从左到右、从右到左分别做一遍这个过程就解决了第一个问题。

对于第二个问题，我们不妨设 f([l,r]) 表示区间 [l,r] 的答案。显然有 f([1,n])=0。然后对于一个大鱼自闭区间 [l,r]，按前文有 f([l,r])=f(M([l-1,r]))+1（当 a_{l-1}\ge a_{r+1}）或者 f([l,r])=f(M([l,r+1]))+1（当 a_{l-1}\lt a_{r+1}），其中 M 表示包含这个区间的最小自闭区间。（按前文引理，包含一个大鱼区间的最小自闭区间是唯一的。）

所以我们只要查询出所有这些 M 然后递推计算就行了。用扫描线+单调栈处理一遍所有大鱼自闭区间即可求出所有需要的 M。

前面所有步骤都是 O(n)，所以这个问题的时间复杂度是 O(n)。