自动搬运

查看原文

来自洛谷，原作者为

	幽云蓝 a

搬运于2025-08-24 22:33:32，当前版本为作者最后更新于2021-08-07 13:34:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是八云蓝的官方题解~

$\textbf{Subtask1}$

读题分，直接大力搜索即可。时间复杂度指数级，具体的蓝没有算。

$\textbf{Subtask2}$

考虑对题意进行转化。我们将所有食材的第 $n+1$ 个食材单独提取出来，然后将区间 $[1,n]$ 的食材从 $n$ 到 $1$ 依次入栈 $A$，将区间 $[n+2,2n+1]$ 的食材从 $n+2$ 到 $2n+1$ 依次入栈 $B$。那么每次取食材操作可以看成取出某一栈栈顶的食材，并将另一栈中的某一食材删除。考虑大力枚举最后挑选出来的评分连续的序列中的最小评分 $l$ 和最大评分 $r$，判断是否存在一种操作方案使得最终可以选出这样一个序列。那么最终我们一定取了评分在区间 $[l,r]$ 内的所有食材，其他的食材可以忽略。考虑将评分在区间 $[l,r]$ 内的左右食材称作关键食材，其余食材称作非关键食材。

现在的任务就是给出若干关键食材，问是否可以将它们全部取到，也可以转化成让它们全部不被删（建立在忽略第 $n+1$ 个食材的情况下哦）。考虑枚举选食材的情况——选非关键删非关键，选关键删非关键，选非关键删关键，选关键删关键。如果选一个非关键的时候只能删除关键食材，那么就说明令一栈中的每个食材都是关键食材，所以可以选另一栈中的关键食材并且删该栈中的非关键食材。于是，可能会导致关键食材被删的情况只有选关键删关键。

考虑使用贪心让选关键食材的时候尽可能可以删非关键。感性理解一下，在删除的过程中，越接近栈底的关键食材越有用，因为不可以通过删关键食材的方式让一个非关键食材接近栈底，并且考虑计算非关键食材 $i$ 的贡献值 $w_i$，代表有多少关键食材满足取某一关键食材时可以删除食材 $i$，那么显然越靠近栈底的食材贡献值就越大，那么删除时就要尽可能保留靠近栈低的关键食材。由此能得出一个贪心策略：① 如果栈顶有两非关键，取一个删另一个；② 如果栈顶有一关键一非关键，取关键删非关键；③ 如果栈顶有两关键，那么取栈 $A$ 栈顶的关键，删栈 $B$ 中最靠近栈顶的非关键，再取栈 $B$ 栈顶的关键，删栈 $A$ 中最靠近栈顶的非关键。如果取某一关键食材的时候不能找出相对应的非关键食材了，那么选出的区间就无解。直接暴力模拟贪心过程是 $O(n^2)$ 的，但是可以通过单调性来 $O(n)$ 模拟。具体来说，取某个关键食材时删除的非关键食材一定在取上方的某个关键食材时删除的非关键食材的下方（感性理解一下吧，严谨证明在题解的最后哦）。

综上，贪心复杂度为 $O(n)$，枚举复杂度为 $O(n^2)$，总复杂度为 $O(n^3)$，可以通过该 subtask。

$\textbf{Subtask3}$

考虑寻找性质。可以发现，如果最后可以取评分在区间 $[l,r]$ 内的所有食材，那么对于该区间的任一子区间，都可以取评分在该子区间内的所有食材。那么容易想到对于每个 $l$，二分数 $r$ 满足可以取评分在区间 $[l,r]$ 内的所有食材，但是不能取区间 $[l,r+1]$ 的食材。二分得到的 $r$ 也可看作一个最大的数 $r$ 满足区间 $[l,r]$ 可以取。时间复杂度为 $O(n^2\log n)$，可以通过该 subtask。

$\textbf{Subtask4}$

考虑寻找更加优秀的性质。记 $m_l$ 代表 $l$ 对应的最大的 $r$ 满足可以取评分在区间 $[l,r]$ 内的所有食材，易证有 $m_l\le m_{l+1}$。使用双指针即可做到 $O(n^2)$ 的复杂度。

$\textbf{Subtask5}$

易得对于任一长度为 $2n+1$ 的初始食材序列有最大满意度小于等于 $n+1$。显然对于该情况能构造出一种取的方法满足最大满意度等于 $n+1$。直接输出 $n+1$ 即可。

$\textbf{Subtask6}$

根据 subtask3，我们可以使用双指针来解决该问题。容易发现指针只会挪动 $n$ 次，每次挪动造成的变化很少，但是在之前的做法中，每次都要重新贪心一遍，复杂度开销巨大。那么现在我们需要一个数据结构使得——可以将某个关键食材变为非关键食材，或者将某个非关键食材变为关键食材，并且要能迅速的根据贪心算出是否可以取所有关键食材。似乎是没有数据结构能直接维护这一贪心，我们继续发掘性质。

我们可以把是否存在解看作一个二分图是否存在完美匹配——记关键食材为黑点，非关键食材为白点，记取某一关键食材，删去另一栈中的某个非关键食材为该关键食材和非关键食材进行匹配。那么我们可以得到两个二分图，二分图 $1$ 代表栈 $A$ 的黑点与栈 $B$ 的白点间的关系，二分图 $2$ 代表栈 $A$ 的白点与栈 $B$ 的黑点间的关系。记点 $i$ 在栈内和栈顶的距离为 $d_i$，蓝先抛出结论：贪心能得到解，相当于对于两张二分图，所有黑点 $x$ 向满足 $d_y\ge d_x$ 的白点 $y$ 连边，都能找出完美匹配。这个也很好证明，在贪心的过程中，容易发现每个黑点都一定与一个 $d$ 比它大的白点进行了匹配。换句话说，如果不存在这样的匹配，那么就意味着贪心得不到解。这等价于对建出的二分图进行二分图匹配，最后看是否有完美匹配。那么直接运用 hall 定理（当然也可以用其他的方式进行推导），我们可以得到贪心是否存在的解 or 二分图是否存在完美匹配的条件：

对于两个栈的每个后缀（即栈底到栈中的某一个元素形成的区间）都有，一个栈的黑色点数量小于等于另一个栈白色点数量，那么解存在，否则解不存在。

上面的问题可以转化成区间加、查询全局 $\min$ 值是否为负数，那么我们就可以使用线段树来维护了。上面的问题还有一个更好的性质，即对于栈 $A$，若其满足其每个后缀的黑色点数量小于等于栈 $B$ 的白色点数量，那么由于一个点不是黑色就是白色，所以栈 $B$ 也满足其每个后缀的黑色点数量小于等于栈 $A$ 的白色点数量。于是最后只需要维护一棵线段树即可。

综上，我们在 $O(n\log n)$ 的时间复杂度内解决了此题。完结撒花~

补：对于上述的贪心，我们有一个严谨的证明（不过使用了最终的结论）。首先，对于最终结论（也就是对于两个栈的每个后缀都有一个栈的黑色点数量小于等于另一个栈白色点数量）满足的情况，容易使用上述的贪心构造一组操作取到所有的黑色点。那么考虑对于两栈的一个长度为 $m$ 的后缀，满足栈 $A$ 的黑点数量 $s1$ 大于栈 $B$ 的白点数量 $s2$。考虑两栈长度为 $n-m$ 的前缀对长度为 $m$ 的后缀的影响。由于黑点必然不会被删除，考虑分类讨论：栈 $A$ 的后缀中的某个白点被删除，此时可能从上方落下一个白点，那么 $s1$ 不变，所以仍有 $s1>s2$，如果落下一个黑色点，那么 $s1$ 加一，仍有 $s1>s2$。如果栈 $B$ 的后缀中的某个白点被删除，此时可能从上方落下一个白点，那么 $s2$ 不变，所以仍有 $s1>s2$，如果落下一个黑色点，那么 $s2$ 减一，仍有 $s1>s2$。综上，如果存在长度为 $m$ 的后缀不满足条件，那么在进行了 $n-m$ 次取食材操作后，两栈 $A$ 和 $B$ 必然仍满足一栈的黑点数大于另一栈的白点数，而这种情况显然是不可能存在合法的方案的。所以最终的结论即合法的取食材方案存在的充分且必要条件。