题解：P11283 「GFOI Round 2」Turtle and Nediam

reinforest · 2025-09-23 18:45:10 · 题解

这篇题解是对 EuphoricStar 的题解的补充。

考虑什么数可能作为中位数。首先，序列的最大值是不可能作为中位数的。不妨把它记为下标 x。

然后把序列分成两段，一段是 [l,x)，另一段是 (x,r]。

我们先考虑第一段数中的一个下标 i，考虑答案 \ge p_i 的判据。

这样做的目的是，如果我们能够找出以上所有可能的 i，那么在这些 p_i 中取 \max 就一定是答案。

可以先考虑一个序列最终只能剩下三个数：p_i，[i,x) 中的最小值（记为 p_t），p_x。首先，我们可以通过 p_t,p_x 删除 (i,x) 中的所有元素（除了 p_t）。

其次，[l,i] 以及 (x,r] 中的所有数都要全删光。若 [i,x) 中的最小值小于 (x,r] 中的最小值，那么不借助 p_x，(x,r] 中的数可以只剩下 (x,r] 中的最小值下标 a，(x,r] 中的最大值下标 b。此时，借助 x,a,b 即可删除 b，借助 t,x,a 即可删除 a。

若 [i,x) 中的最小值小于 [l,i] 中的最小值，那么 [l,i] 中的数也与上同理的方式就可以删光（除了 p_i）。

假设我们已经把 [l,i] 或者 (x,r] 进行了如上操作，我们也可以先不借助 p_x，把它删成最小值下标 a，最大值下标 b。这个时候，若 p_a<p_t（p_t 是 [i,x) 中的最小值），我们可以先把 p_t 借助 t,x,a 删除，接下来只剩三个下标 i,a,x，中位数刚好是 p_i。

从以上的表述可知，当 [l,i] 中的最小值小于 [i,x] 中的最小值，需要借助 p_t 的删除才能删除 [l,i] 中的所有数，(x,r] 同理。

从以上的表述可知，最终剩下三个数的中位数刚好是 i，因为 p_t 只能使用一次，需要保证 [i,x] 的最小值小于 [l,i] 中的最小值或者 (x,r] 中的最小值。

现在对于一个区间 [l,r]，我们需要找出所有符合条件的 i，并用它们的 p_i 取 \max。首先求出最大值下标 x。然后求出 [l,x] 中的最小值下标 a，以及 [x,r] 中的最小值下标 b。

• 若 [i,x] 的最小值小于 [l,i] 中的最小值，我们需要保证 i \leq a。
• 若 [i,x] 的最小值小于 (x,r] 中的最小值，我们需要求出在 z 前第一个比 z 小的数 L_z，然后我们需要保证 i \leq L_z。L 数组可以通过单调栈求出。

这两个范围是或的关系。求出范围取区间最大就行。

注意我们现在的讨论都在 i \in [l,x) 的范围内。但是 i \in (x,r] 是同理的。

• 若 [x,i] 的最小值小于 [i,r] 中的最小值，我们需要保证 i \ge b。
• 若 [x,i] 的最小值小于 [l,x] 中的最小值，我们需要求出在 y 后第一个比 z 小的数 R_z，然后我们需要保证 i \ge R_z。R 数组也可以通过单调栈求出。

这两个范围是或的关系。求出范围仍然取区间最大就行。

然后这道题就做完了。