Half Selection Game

解説

Bob がどのように操作しても Alice が $Y$ を区間 $[L, R]$ に収められる範囲を考えます。
区間の下端 $L$ を固定して、条件を満たす最小の上端 $R$ を求めます。

ゲームの各状態を頂点とし、前半・後半を選んだ状態を左右の子とする二分木を作ります。葉は各要素 $A_i$ に対応します。

各頂点にはその状態から Alice が $L \le Y \le R$ を保証できる最小の $R$ を持たせます。（保証できない場合は $\infty$ とします。）

葉 $i$ の値は以下の通りです。

$$\begin{aligned} \begin{cases} A_i & (\text{if ~ $A_i \ge L$}) \\ \infty & (\text{if ~ $A_i \lt L$}) \end{cases} \end{aligned}$$

また、各頂点では左右の子の値を $u, v$ とすると以下の通りです。

$$\begin{aligned} \begin{cases} \min(u, v) & (\text{if ~ Alice の手番}) \\ \max(u, v) & (\text{if ~ Bob の手番}) \end{cases} \end{aligned}$$

根からの深さが偶数なら Alice の手番、奇数なら Bob の手番です。

そしてこの二分木は、以下の手続きで差分更新を行うことができます。

1. はじめ、すべての葉の値を $\infty$ とする。
2. $A$ を降順にソートしたものを $A'$ とする。 $L = A'_1, A'_2, \cdots, A'_N$ の順に以下の操作を行う。
   • $A_i = L$ となる各 $i$ に対して、葉 $i$ の値を $L$ に更新する。
   • その後、対応する葉の各祖先を更新する。

今まで出現した根の $R - L$ の値としてあり得る最小値を $W$ としたとき、答えは $\lceil W / 2 \rceil$ となります。

木の高さは $O(\log N)$ となるため、全体の計算量は $O(N \log N)$ です。