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

这篇题解是对 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 \in [l,x)$ 的范围内。但是 $i \in (x,r]$ 是同理的。

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

然后这道题就做完了。