今回の問題は ゲーム理論 をテーマとした問題です。
今回は問題文の <details> (折り込み部分) に但し書きがついていました。

各段階でプレイヤーはその時点までに公開されている情報に基づいて可能な選択肢それぞれに合計が \(1\) となるように確率を割り当て、その確率に従ってランダムに \(1\) つ選ぶ戦略を取る。
プレイヤーは、「勝率としてありうる最小値」、すなわち「相手が自身の勝率を最小化するような戦略を選んだ時の勝率」を最大化する戦略を選ぶ。条件を満たす戦略の選び方が複数ある場合はどれを選んでも良い。
両者がこの方針に従って行動した時、戦略の選び方によらず高橋君の勝率は一意に定まる。この値を求めよ。

まずはこの但し書きの内容および正当性をきちんと説明することを目的として、必要な知識の概観を行います。

二人零和ゲーム

次のルールに従うゲームを 二人零和ゲーム (二人ゼロ和ゲーム, 二人ゼロサムゲームとも) と定義することにします。

• プレイヤーの数は \(2\) 人
• 各プレイヤーが \(1\) 回だけムーブを選び、その結果に応じて各プレイヤーの利得が定まる
• 各プレイヤーはムーブを取る際に相手がどのムーブを取るかわからない
• 各プレイヤーの取り得るムーブは有限個
• ゲームの結果についての両プレイヤーの利得の和は \(0\)

今回の問題のように自身の勝率を最大化することを目的とするゲームは、勝率を利得関数とすると (二人の勝率の和) \(= 1\) なのでゼロサムではありませんが、和が定数なので適切な変形により二人零和ゲームと同一視して問題ないことが確認できます。
また、今回の問題は複数回ムーブを選ぶ段階がある (BAN 段階とデッキ選択段階) ゲームですが、各段階は同時にムーブを選ぶ形式なので、後ろの段階から順に二人零和ゲームとして解析していくことができるため問題ないです。
以降では二人零和ゲームの性質について取り扱います。(以降では単に零和ゲームと呼びます)

混合戦略

通常、競技プログラミングで出題されるゲーム問題では、プレイヤーは１つのムーブを選ぶことが最適な、すなわち勝率を最大化する戦略となります。これを 純粋戦略 と呼びます。
しかし、零和ゲームでは「相手がどのムーブを取り得るかわからない」という都合上、純粋戦略が必ずしも勝率を最大化する戦略にはなりません。
これはじゃんけんを考えるとわかりやすいです。じゃんけんの戦略として「グーを \(100 \%\) 出し続ける」という戦略を最適だと主張する人はいないでしょう。なぜならこの戦略はパーを好んで出す人相手だと分が悪い戦略であることが明らかだからです。
そこで、複数のムーブに確率を割り当ててランダムに 1 つを選ぶという戦略を考えてみましょう。これを 混合戦略 と呼びます。

問題文の但し書きの \(1\) 行目の

各段階でプレイヤーはその時点までに公開されている情報に基づいて可能な選択肢それぞれに合計が \(1\) となるように確率を割り当て、その確率に従ってランダムに \(1\) つ選ぶ戦略を取る。

という箇所は混合戦略のことを説明していたことになります。以降では混合戦略のことを単に「戦略」と呼びます。

マクシミン戦略

次は問題文の但し書きの 2 行目の

プレイヤーは、「勝率としてありうる最小値」、すなわち「相手が自身の勝率を最小化するような戦略を選んだ時の勝率」を最大化する戦略を選ぶ。

という箇所について説明していきます。これは マクシミン戦略 と呼ばれる戦略を説明した文章です。

まずいくつかの式の定義を行います。
以降ではゲームのプレイヤーをそれぞれ Alice, Bob と呼びます。

\[\Delta_n = \left\lbrace x=(x_1, x_2, \dots, x_n)^T \vert \sum_{i=1}^n x_i = 1, x_i \geq 0 \right\rbrace\]

とします。つまり \(\Delta_n\) は \(n\) 択から選ぶことのできる混合戦略からなる集合です。
利得行列 \(A\) を \((i, j)\) 成分が「Alice がムーブ \(i\) を、Bob がムーブ \(j\) を選んだ時の Alice の利得」となるように定義した行列とします。
零和ゲームの利得行列が \(n \times m\) 行列 \(A\) によって表されるとき、利得関数 \(E(x, y)\) \((x \in \Delta_n, y \in \Delta_m)\) を「Alice が混合戦略 \(x\) を、Bob が混合戦略 \(y\) を取ったときの利得の期待値」として定義します。つまり、

\[E(x, y) = x^{T} A y\]

が成り立ちます。以降でも暗黙裡に \(x\) を Alice の混合戦略、\(y\) を Bob の混合戦略として用います。

さて、以上の定式化を踏まえた上で、Alice が『「利得としてありうる最小値」、すなわち「相手が自身の利得を最小化するような戦略を選んだ時の利得」を最大化する戦略」』を取ることを考えます。 「相手が自身の勝率を最小化するような戦略を選んだ時の勝率」は

\[\min_y E(x, y)\]

になりますから、これを最大化する戦略およびその時の利得は

\[\argmax_x \min_y E(x, y), \max_x \min_y E(x, y)\]

になります。これを マクシミン戦略 と呼びます。(注：\(\argmax_x\) は最大値を達成する戦略全体の集合を表す。集合の要素が複数ある場合はその中から任意に \(x\) を \(1\) 個選べばよい。)

Bob も同様の戦略で動くと

\[\max_y \min_x -E(x, y)\]

を得ますが、ここで零和ゲームの性質からこの時の Alice の利得は式全体を \(-1\) 倍した

\[\min_y \max_x E(x, y)\]

になります。こちらの方が符号が揃っていて扱いやすいので以降ではこの式で Bob の戦略を考えることにします。

簡潔にまとめると、

• Alice は \(\argmax_x \min_y E(x, y)\) を選び、
• Bob は \(\argmin_y \max_x E(x, y)\) を選ぶ

ということになります。これが問題文の但し書きの 2 行目の内容です。

ミニマックス定理

最後に問題文の但し書き 3 行目を見てみましょう。

両者がこの方針に従って行動した時、戦略の選び方によらず高橋君の勝率は一意に定まる。

「勝率が一意に定まる」ということを定式化すると、

\[\max_x \min_y E(x, y) = \min_y \max_x E(x, y)\]

を意味します。これを ミニマックス定理 と呼びます。
まずはミニマックス定理の正当性を線形計画問題を経由して確認しましょう。

まず、Alice 側の戦略を線形計画問題として表してみましょう。求めたいものは

\[\max_x \min_y x^{T} A y\]

です。\(x\) を固定した時の \(x^{T} A y\) を最小化する \(y\) は純粋戦略のみを考えればよい (\(y\) に対して線形な式であるため) ことを踏まえると、以下の式を得ます。

\[ \begin{aligned} \max. & & \min_j \sum_{i=1}^n A_{i,j} x_i \\ \mathrm{s.t.} & & \sum_{i=1}^n x_i = 1 \\ & & x_i \geq 0 \end{aligned} \]

\(\min_j \sum_{i=1}^n A_{i,j} x_i = v\) と置くと

\[ \begin{aligned} \max. & & v \\ \mathrm{s.t.} & & v - \sum_{i=1}^n A_{i,j} x_i \leq 0 & & (\forall j) \\ & & \sum_{i=1}^n x_i = 1 \\ & & x_i \geq 0 \end{aligned} \]

を得ます。
この線形計画問題の双対を取りましょう。上から \(y_j, w\) を変数として割り当てると

\[ \begin{aligned} \min. & & w \\ \mathrm{s.t.} & & w - \sum_{j=1}^m A_{i,j} y_j \geq 0 & & (\forall i)\\ & & \sum_{j=1}^m y_j = 1\\ & & y_j \geq 0 \end{aligned} \]

\(w = \max_i \sum_{j=1}^m A_{i,j} y_j\) としても良いことが確認できるので、\(w\) を消去して

\[ \begin{aligned} \min. & & \max_i \sum_{j=1}^m A_{i,j} y_j \\ \mathrm{s.t.} & & \sum_{j=1}^m y_j = 1\\ & & y_j \geq 0 \end{aligned} \]

この式は \(\min_y \max_x x^{T} A y\) と一致しています！

競技プログラミングの知識を前提とすると、実行可能解が存在して有界である時に線形計画問題の主問題と双対問題の解が一致することは有名事実ですから、

\[\max_x \min_y E(x, y) = \min_y \max_x E(x, y)\]

が従ったことになります。

さて、以上の議論を踏まえた上で、但し書きの 3 行目、

両者がこの方針に従って行動した時、戦略の選び方によらず高橋君の勝率は一意に定まる。

の部分を証明します。(注：ここで「一意」なのは得られる勝率の値であり、最適戦略そのものは一意とは限らない。)

(証明) \(x^{\ast}\) を主問題の最適解、\(y^{\ast}\) を双対問題の最適解をそれぞれ任意に取ったものとする。(任意に取る部分が「戦略の選び方によらず」に対応している。)また \(V\) を線形計画問題の最適値とする。このとき

• \(\forall j, \sum_{i=1}^n A_{i,j} {x_i}^{\ast} \geq V \to A^{T}x^{\ast} \geq V \mathbf{1}\)
• \(\forall i, \sum_{j=1}^m A_{i,j} {y_j}^{\ast} \leq V \to Ay^{\ast} \leq V \mathbf{1}\)

が成り立つ。各式にそれぞれ \((y^{\ast})^T, (x^{\ast})^T\) を左から掛けると

\[(y^{\ast})^T A^{T}x^{\ast} \geq (y^{\ast})^T V \mathbf{1} = V\]

\[(x^{\ast})^T Ay^{\ast} \leq (x^{\ast})^T V \mathbf{1} = V\]

を得る。よって

\[V \leq (x^{\ast})^T Ay^{\ast} \leq V \iff (x^{\ast})^T Ay^{\ast} = V\]

となり、最適解の選び方によらず最適値は一定であることが示された。(証明終わり)

なお、これは余談ですが、任意の関数 \(f(x, y)\) について

\[\max_x \min_y f(x, y) \leq \min_y \max_x f(x, y)\]

が成り立つことは比較的に簡単に示せます。(ミニマックス不等式)

(証明) \(\forall x, \min_y f(x, y) \leq f(x, y)\) かつ \(\forall y, f(x, y) \leq \max_x f(x, y)\) が成り立つので

\[\forall x, \forall y, \min_{y'} f(x,y') \leq \max_{x'} f(x',y)\]

を得る。上式の左辺を \(x\) で最大化、右辺を \(y\) で最小化して所望の式を得る。(証明終わり)

ナッシュ均衡

以上の議論により、問題文の但し書きの正当性が示されて、目的は達成されました。しかし、「なぜ混合戦略を考えたのか？」「なぜマクシミン戦略を考えたのか？」というある種の意味論的な疑問が残っている方も多いのではないのかと思います。
この章ではナッシュ均衡を説明して、今回の問題で求めたい戦略対がナッシュ均衡と一致することを証明します。

ナッシュ均衡 (正確には混合戦略におけるナッシュ均衡、混合戦略ナッシュ均衡) とは、次の条件を満たす戦略対 \((x^{\ast}, y^{\ast})\) を言います：

• \(\forall x, E(x^{\ast}, y^{\ast}) \geq E(x, y^{\ast})\) かつ \(\forall y, E(x^{\ast}, y^{\ast}) \leq E(x^{\ast}, y)\)

言葉で説明すると次のようになります：

• Bob の戦略が \(y^{\ast}\) のとき、Alice は戦略を \(x^{\ast}\) から変えても得しない
• Alice の戦略が \(x^{\ast}\) のとき、Bob は戦略を \(y^{\ast}\) から変えても得しない

ナッシュ均衡は、各プレイヤーが自分にとって最適な行動を選択していて、誰もそこから戦略を変更する動機を持たない安定状態であることから、最適戦略としてはある意味もっとも自然な定義であると考えられます。

ここで、零和ゲームにおいて次の事実が成り立ちます。

戦略対 \((x^{\ast}, y^{\ast})\) について次は同値：

1. \((x^{\ast}, y^{\ast})\) はナッシュ均衡
2. \(x^{\ast}\) は \(\min_y E(x, y)\) を最大化する \(x\) で \(y^{\ast}\) は \(\max_x E(x, y)\) を最小化する \(y\) である。(つまり、問題文の但し書きの方針で選んだ戦略である。)

(証明)

(1) \(\to\) (2) : \((x^{\ast}, y^{\ast})\) をナッシュ均衡とする。\(v = E(x^{\ast}, y^{\ast})\) とする。

ナッシュ均衡の条件式から任意の \(x\) について

\[E(x^{\ast},y^{\ast}) \geq E(x, y^{\ast})\]

が成り立つので、

\[\min_y E(x, y) \leq E(x, y^{\ast}) \leq v\]

となり、両辺を \(x\) で最大化して

\[\max_x \min_y E(x, y) \leq v\]

を得る。同様にしてナッシュ均衡の条件式から任意の \(y\) について

\[E(x^{\ast},y^{\ast}) \leq E(x^{\ast}, y)\]

が成り立つので、

\[\max_x E(x, y) \geq E(x^{\ast}, y) \geq v\]

となり、両辺を \(y\) で最小化して

\[\min_y \max_x E(x, y) \geq v\]

を得る。つまり

\[\max_x \min_y E(x, y) \leq v \leq \min_y \max_x E(x, y)\]

となるが、ミニマックス定理により両辺は等しいので

\[\max_x \min_y E(x, y) = \min_y \max_x E(x, y) = v\]

となる。そしてこの等号が成立する時に

\[v = \min_y E(x^{\ast}, y) = \max_x E(x, y^{\ast})\]

が成り立つので、\(x^{\ast}, y^{\ast}\) は (2) の条件を満たす。

(2) \(\to\) (1) : \(V:=\max_x \min_y E(x, y)\) とおく。定義より

\[\max_x E(x, y^{\ast}) = \min_y E(x^{\ast}, y) = V\]

であり、また先の議論により

\[E(x^{\ast}, y^{\ast}) = V\]

である。さらに

\[E(x, y^{\ast}) \leq \max_x E(x, y^{\ast}), E(x^{\ast}, y) \geq \min_y E(x^{\ast}, y) \]

であるから

\[\forall x, \forall y, E(x, y^{\ast}) \leq E(x^{\ast}, y^{\ast}) \leq E(x^{\ast}, y)\]

を得て、これはナッシュ均衡の定義式と一致する。(証明終わり)

このように、問題文に定義される戦略対は実はナッシュ均衡という最も自然な戦略対と一致することが言えました。
また、次の事実も成り立ちます。

混合戦略を認める零和ゲームではナッシュ均衡が必ず存在する。

証明については、これまでに議論した通り、零和ゲームのナッシュ均衡は問題文に定義される戦略対と等しいため線形計画問題として定式化できること、および有界で実行可能解を持つ線形計画問題は最適解を持つことから示されます。
零和ゲームは純粋戦略だけを認めるとナッシュ均衡が存在しないことはじゃんけんの例を考えると明らかです。混合戦略を認めることでナッシュ均衡が必ず存在する点は非常に興味深く、これが混合戦略を考える意義であると言えるでしょう。　

さて、長くなりましたがこの問題の関連知識の説明を終えて本題に入りたいと思います。

解法

\(V_{i,j}\) を \(A_i\) と \(B_j\) を BAN した時の高橋君の最適勝率として定義します。\(V_{i,j}\) は \((N-1) \times 2\) 行列で表せる零和ゲームの最適解です。\(V_{i,j}\) が全て計算できれば、最初の BAN 段階は \(3 \times N\) 行列で表せる零和ゲームとなります。よって

• \(V_{i,j}\) を全て計算する
• \(3 \times N\) 行列で表せる零和ゲームを解く

という 2 段階の計算によってこの問題を解くことが出来ます。

まずは \(V_{i,j}\) の計算を考えます。
\(j\) ごとに別々に計算することにします。\(j=3\) の場合を説明します。(ほかの \(j\) でもやることは同じです。) \(V_{i,j} = v_i\) と置き直します。求めたいものは \(v_1, v_2, \dots, v_N\) です。
ここで青木君が \(B_1\) を使う確率を \(x\) と置くことにします。すると

\[ \begin{aligned} v_i &= \min_{0 \leq x \leq 1} \max_{k\neq i} p_{k,1} x + p_{k,2} (1-x) \\ &= \min_{0 \leq x \leq 1} \max_{k\neq i} (p_{k,1} - p_{k,2}) x + p_{k,2} \end{aligned} \]

が成り立つので、直線 \(L_k\) を \(y = (p_{k,1}-p_{k,2}) x + p_{k,2}\) として定義した時、

• \(v_i\) \(=\)(直線 \(L_i\) 以外の \(N-1\) 本の直線からなる上包絡線の \(0 \leq x \leq 1\) における最小値)

となります。この \(v_1, v_2, \dots, v_N\) を列挙する問題を部分問題と呼ぶことにします。
\(v_i\) を 1 個だけ求めるのであれば包絡線を求めるアルゴリズムを用いれば \(\mathrm{O}(N \log N)\) で計算できますが、今回は \(N\) 個の値を求める必要があるので工夫が要ります。
部分問題はいくつかの解法がありますが、ここでは 2 種類の解法を説明します。

部分問題の解法 1 : 包絡線の性質を利用する解法

想定解は包絡線の性質から従う非常にシンプルな解法です。
まず、\(L_1, L_2, \dots, L_N\) からなる上包絡線を求めます。このとき、上包絡線が \(0 \leq x \leq 1\) において最小値を取る座標を \(1\) つ取ってきて \((x_0, y_0)\) とします。このとき、次の事実が成り立ちます：

• サイズ \(2\) 以下の直線の集合 \(S\) が存在して、\(L_k \not \in S\) のとき \(v_k = y_0\) が成り立つ。

例えば \((x_0, y_0)\) において交わる直線が \(L_i, L_j\) の 2 本だけであった場合は \(S = \lbrace L_i, L_j \rbrace\) が条件を満たすことが証明できます。(証明は省略しますが、図を書いてみると直感的に理解しやすいです。) \((x_0, y_0)\) において直線が \(3\) 本以上交わっている場合や最小値を取る \(x\) 座標が区間となる場合、および \(x_0=0\) または \(x_0=1\) の場合でも、適切な議論により \(2\) 本以下の直線を除くと \(v_k = y_0\) が成り立つことが証明できます。

この事実を用いると、次の方針で \(\mathrm{O}(N \log N)\) で問題を解く案が浮かびます：

• \((x_0, y_0)\) および \(S\) を求める
• \(i \in S\) における \(v_i\) は個別に計算して、それ以外の \(v\) は \(v=y_0\) とする

この解法は適切な実装により正確に動作します…が、この解法は誤差に対して鋭敏であるため、正確に実装するためには複数個所で発生する計算誤差に適切に対処する必要があり、この方針で通し切るには計算幾何学への深い理解が必要となるでしょう。あるいは今回の問題は有理数で全ての計算を処理できるので有理数を値とした幾何ライブラリを使用することも視野に入るかもしれません。

部分問題の解法 2 : 永続動的 Li Chao Tree を用いる解法

別解として 永続動的 Li Chao Tree という強力なデータ構造を用いる解法を紹介します。
まず永続動的 Li Chao Tree の定義を行います。Li Chao Tree に関する説明は割愛します。通常の Li Chao Tree は木の形があらかじめ定まっていますが、アルゴリズムを拡張すると木の形が追加された直線に応じて定まる動的な Li Chao Tree を考えることが出来ます。(動的セグ木・疎なセグ木をイメージするとわかりやすいでしょう。) ただし、追加される直線によっては木の深さが追加した直線の本数に依存することになり計算量に問題が生じるので「再帰の深さを \(50\) 程度で打ち切る」などの深さ制限を設ける必要がある点に注意してください。

• この時、深さ制限により本来必要な直線が捨てられることによる誤差は極めて微小です。特に今回の問題では区間が \([0,1]\) 、直線の傾きが \([-1,1]\) の範囲に収まるので再帰の深さを \(D\) で打ち切ると誤差が \(2^{-D}\) 以下となることが保証されます。

このようにして定義される動的 Li Chao Tree は永続化が容易で、永続化したものが永続動的 Li Chao Tree です。
永続動的 Li Chao Tree は以下の操作ができます(深さの最大値を \(D\) とおきます)：

• add_line(a, b) : 直線 \(y = ax + b\) を追加する。\(\mathrm{O}(D)\)
• get_max(x): \(\displaystyle \max_{f : 追加した直線} f(x)\) を求める。\(\mathrm{O}(D)\)
• copy() : Li Chao Tree を複製する。 \(\mathrm{O}(1)\)

永続動的 Li Chao Tree を用いると今回の \(v_i\) の計算を容易に行えます。

• \(s_i\) : \(L_1, L_2, \dots, L_i\) を追加した Li Chao Tree
• \(t_i\) : \(L_i, L_{i+1}, \dots, L_N\) を追加した Li Chao Tree

とします。\(s_i, t_i\) は累積和の要領で木の複製と直線の追加を繰り返せば効率的に計算できます。このように \(s, t\) を列挙すると、\(x'\) を固定した時の「直線 \(L_i\) 以外の \(N-1\) 本の直線からなる上包絡線の \(x=x'\) における \(y\) 座標」が \(s_{i-1}\) と \(t_{i+1}\) にクエリを投げることでただちに取得できます。よって、上包絡線の凸性を利用した三分探索を行えば上包絡線の最小値が求まります。よって \(v_1, v_2, \dots, v_N\) を三分探索 1 回あたりの反復回数を \(S\) 、深さの最大値を \(D\) として \(\mathrm{O}(N S D)\) 程度で求められました。

なお、他にも \(V_{i,j}\) を列挙する方法は考えられます。詳細は省略しますが方針を列挙すると次の通りです。

• 2nd-max を管理できる Li Chao Tree を用いる方法
• Line Container と呼ばれるデータ構造を永続化する方法
• Seidel’s LP algorithm で basis を列挙する方法(詳細は自分も知りません…)

さて、以上の方法で \(V_{i,j}\) を全て計算できました。次は \(V_{i,j}\) を係数とする \(3 \times N\) 行列を係数とする零和ゲームを解けばよいです。
この問題も様々な解法があります。今回は部分問題と異なり \(\mathrm{O}(N)\) や \(\mathrm{O}(N \log N)\) 掛けて計算しても良いので、例えば

• 種々の線形計画問題を解くアルゴリズムを利用する
• 解の値で二分探索をして halfplane intersection に帰着させる

などの手法で解くことが出来ます。ここでは問題の特性を生かした容易な解法を説明します。
まず、\((V_{i,1}, V_{i,2}, V_{i,3})\) の種類数が \(\mathrm{O}(1)\) 種類しかないことが「部分問題の解法 1」における議論により確認できます。(各 \(j\) について \(v_i \neq y_0\) となる \(i\) は定数個であることから従います。) 重複する列を削除しても零和ゲームの解は変わらないので削除すると、\(3\) 行 \(\mathrm{O}(1)\) 列の零和ゲームを解けばよいことになります。
これは \(3\) 変数 \(\mathrm{O}(1)\) 式の線形計画問題と等価です。ここで線形計画問題の凸性から、 三分探索を二重に行えば最適値を求められることが証明できます。

(証明) \(x = (\lambda, v_1, \dots, v_n) \in R^{n+1}\) を変数として目的関数 \(\mathrm{LP}(x)\) を最大化する線形計画問題を考えます。\(\lambda\) の値を固定した時の \(\mathrm{LP}(x)\) の最適値を \(f(\lambda)\) と置きます。\(f(\lambda)\) の凸性を示せればよいです。
\(\lambda=\lambda_1, \lambda_2\) と固定した時の LP の最適解を \(x_1, x_2\) と置きます。また \(0 \leq \alpha \leq 1\) とします。
\(x_3 = \alpha x_1 + (1-\alpha) x_2\) と置きます。この時、制約条件は全て線形関数であることから \(x_3\) は実行可能解であることが確認できます。 また、この時の \(\lambda\) は \(\alpha \lambda_1 + (1-\alpha) \lambda_2\) です。

\[\mathrm{LP}(x_3) = \alpha \mathrm{LP}(x_1) + (1-\alpha) \mathrm{LP}(x_2)\]

が成り立ちます。よって、

\[ \begin{aligned} f(\alpha \lambda_1 + (1-\alpha) \lambda_2) &\geq \mathrm{LP}(x_3)\\ &= \alpha \mathrm{LP}(x_1) + (1-\alpha) \mathrm{LP}(x_2) \\ &= \alpha f(\lambda_1) + (1-\alpha) f(\lambda_2) \end{aligned} \]

が成り立ちます。この式から \(f(\lambda)\) が上に凸であることが言えるので、示されました。(証明終わり)

以上の内容を適切に実装することでこの問題を解くことが出来ます。計算量は解法によりますが、想定解では三分探索 1 回あたりの反復回数を \(S\) として \(\mathrm{O}(N \log N + S^2)\) 程度で解くことができて十分高速です。(有理数幾何や永続動的 Li Chao Tree などの計算量が大きめな解法に配慮して制約をかなり緩めに設定しています。)