No.335

調べる宝くじの数値を $E_i$ とする.

発表された2つの数値を $E_i, E_j$ として, $L = \{E_0,E_1,\dots,E_{i-1}\},\ C = \{E_{i+1},E_{i+2},\dots,E_{j-1}\},\ R = \{E_{j+1},E_{j+2},\dots,E_{N-1}\}$ として, 得られる最大の金額を考える. 以下 $L_M = \max(L),\ L_m = \min(L)$ ($C, R$ も同様) とする.

$E_i \lt E_j$ の場合は以下の最大値が得られる最大の金額である.

• $L$ から数値を選ぶとすると, $L_M \gt E_i$ の場合は $\max(L_M, E_j)$, そうでない場合は $0$.
• $C$ から数値を選ぶとすると, $C_M \gt E_j$ の場合は $C_M$, $C_m \lt E_i$ の場合は $E_j$, いずれでもない場合は $0$.
• $R$ から数値を選ぶとすると, $R_m \lt E_j$ の場合は $E_j$, そうでない場合は $0$.

$E_i \gt E_j$ の場合も同様に以下の最大値が得られる最大の金額である.

• $L$ から数値を選ぶとすると, $L_m \lt E_i$ の場合は $E_i$, そうでない場合は $0$.
• $C$ から数値を選ぶとすると, $C_M \gt E_i$ の場合は $C_M$, $C_m \lt E_j$ の場合は $E_i$, いずれでもない場合は $0$.
• $R$ から数値を選ぶとすると, $R_M \lt E_i$ の場合は $\max(R_M, E_i)$, そうでない場合は $0$.

これを $i, j$ を動かしながら計算するのだが, 興味があるのは $L, C, R$ ともに最大値と最小値のみであるので, 最初に Sparce Table を作っておけば, 区間内の最大/最小は $O(1)$ で計算できる.