题目大意

给你一个序列，A 和 B 一次轮流操作，A 希望答案剩余的最大，B 希望答案最小，但是所有的操作都需要满足操作实在端点。

对于 $\forall k\in[1,n]\cap \mathbb{Z}$ ，重新开始一局游戏，A 先在满足要求的情况下选取 $k$。

其中数据范围满足，$1\le n\le 3\times 10^5$。

思路

某大佬曾经说过，如果一方用一个简单的操作就能达到某种结果，那他的最终结果不会更差。

对于权值博弈则可以延申为：如果先手能保证不小于某个值，后手能保证不大于某个值，那么答案就是这个。

定义 $mid=\lfloor \dfrac{1+n}{2}\rfloor$，那么对于 $k=0$ 的情况，答案的取值如下：

$ans=\left\{\begin{matrix} \max(a_{mid},a_{mid+1}) & n\text{ is even}\\ \max(\min(a_{mid},a_{mid-1}),\min(a_{mid},a_{mid+1})) & n\text{ is odd} \end{matrix}\right.\mathbb{}$

先证明 $n$ 是偶数是的正确性：

首先 A 可以选择 $a_{mid},a_{mid+1}$ 中最大值的位置 $p$ 与 $1,n$ 中距离较远的位置选择，接着和 B 进行对称的操作，这样就可以保证在选择了 $n-2$ 次只剩 $a_{p-1},a_p$ 或者 $a_p,a_{p+1}$。

接着 A 只需要选择 $a_{p-1}$ 或者 $a_{p+1}$ 就一定可以剩余 $a_p$。

根据某个某个大佬总结的性质，因为 A 可以将答案牢牢控制在 $a_p$，所以这一定是最优解。

再证明 $n$ 是奇数的情况的正确性：

首先 A 可以选择 $a_1$ 或者 $a_n$，那么问题就转化为了 $n$ 是偶数的情况，区别只有 B 希望答案更小。

同样的，B 可以使用上面的方法将最后的取值控制在 $\min(a_{mid'},a_{mid'+1})$，其中 $mid'$ 为 A 选择后中间的位置。

容易得到 $mid'=mid$ 或 $mid'=mid-1$，所以答案就是 $\max(\min(a_{mid},a_{mid-1}),\min(a_{mid},a_{mid+1}))$。

对于 $k\ne 0$ 的情况，容易想出 A 率先吃肯定只有 $mid$ 的值会受到影响，考虑计算出每一个 $k$ 可以影响的 $mid$ 的取值取值范围。

对于 $k$ 个全部取在左边的情况，$mid=\lfloor \dfrac{n-k+1}{2}\rfloor+k$ 。

同理对于 $k$ 全部取在右边的情况，$mid=\lfloor \dfrac{n-k+1}{2}\rfloor$。

设 $x=\lfloor \dfrac{n-k+1}{2}\rfloor$，那么答案为：

$\left\{\begin{matrix} \max \limits _{{\tiny i=\lceil \dfrac{n-k}{2}\rceil }}^{{\tiny \lceil \dfrac{n+k}{2}\rceil}} a_i& n-k\text{ is odd}\\ \max \limits_{{\tiny i=\lfloor \dfrac{n-k}{2}\rfloor -1}}^{{\tiny \lfloor \dfrac{n+k}{2}\rfloor}} (\min(a_{i},a_{i+1}))&n-k\text{ is even} \end{matrix}\right.$

另外 $k=n-1$ 的情况需要特判，应为在 A 拿完之后游戏就直接结束了，所以答案为 $\max\limits_{i=1}^{n}a_i$。

Submission #273106358 - Codeforces