考虑使用贪心让选关键食材的时候尽可能可以删非关键。感性理解一下，在删除的过程中，越接近栈底的关键食材越有用，因为不可以通过删关键食材的方式让一个非关键食材接近栈底，并且考虑计算非关键食材 i 的贡献值 w_i，代表有多少关键食材满足取某一关键食材时可以删除食材 i，那么显然越靠近栈底的食材贡献值就越大，那么删除时就要尽可能保留靠近栈低的关键食材。由此能得出一个贪心策略：① 如果栈顶有两非关键，取一个删另一个；② 如果栈顶有一关键一非关键，取关键删非关键；③ 如果栈顶有两关键，那么取栈 A 栈顶的关键，删栈 B 中最靠近栈顶的非关键，再取栈 B 栈顶的关键，删栈 A 中最靠近栈顶的非关键。如果取某一关键食材的时候不能找出相对应的非关键食材了，那么选出的区间就无解。直接暴力模拟贪心过程是 O(n^2) 的，但是可以通过单调性来 O(n) 模拟。具体来说，取某个关键食材时删除的非关键食材一定在取上方的某个关键食材时删除的非关键食材的下方（感性理解一下吧，严谨证明在题解的最后哦）。
根据 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 必然仍满足一栈的黑点数大于另一栈的白点数，而这种情况显然是不可能存在合法的方案的。所以最终的结论即合法的取食材方案存在的充分且必要条件。