[0] 定義

整数 \(i,\ x\ (1 \le i \le N^2,\ 1\leq x \le S)\) に対し、 \(A_{j}=x,\ j < i\) が成り立つ最大の \(j\) を \(\mathrm{behind}(i,x)\) と書きます（そのような \(j\) が存在しない場合、 \(\mathrm{behind}(i,x)=0\) とします）。また、 \(A_{j}=x,\ i < j\) を満たす最小の \(j\) を \(\mathrm{front}(i,x)\) と書きます（そのような \(j\) が存在しない場合、\(\mathrm{front}(i,x)=\infty\) とします）。これらについては \(O(N)\) で前処理を行うことで \(O(\log N)\) で求めることができます。

長さ \(n\) の整数列 \(X=(X_1,\ X_2,\ \dots,\ X_n)\) に対し、以下が成り立つ最大の \(s\) を \(f(X)\) と書きます。

• 総和が \(s\) であるような任意の正整数列 \(Y\) が \(X\) の部分列となる。

---

[1] 動的計画法

\(dp_i=f((A_1,\ A_2,\ \dots,\ A_i))\) として \(i=1,\ 2,\ \dots\) の順に求めていきます。便宜上 \(dp_{-1}=-1,\ dp_0=0\) とします。

総和が \(S\) であるような整数列のうち、最終項が \(x\) であるものは (総和が \(S-x\) である整数列) \(+(x)\) と考えることができます。このため、総和が \(S\) である整数列のうち、最終項が \(x\) であるものがすべて部分列になっている条件は \(S-x \leq dp_{\mathrm{behind}(i,x)-1}\) です。

このことから \(\displaystyle dp_i=\min_{1\leq x \leq S} (dp_{\mathrm{behind}(i,x)-1}+x)\) が成り立ちます。

---

[2] 必要な部分だけ求める

上記の動的計画法ではすべての \(-1 \le i \le N^2\) に対して \(dp_i\) を求めていますが、\(dp_i\) は \(i\) について単調であることから各 \(-1 \leq s \leq S\) に対し \(dp_i=s\) となる最小の \(i\) さえ求まっていればいいです（末尾が \(x=1\) である正整数列を考えると、このような \(i\) は必ず存在することがわかります）。計算の際 \(dp_i\) が必要な場合は二分探索で求められます。

現在 \(dp_{i}=s\ (s < S)\) がわかっているとき、\(dp_{i'}=s+1\) となる最小の \(i'\) の求め方を考えます。 \(dp_{\mathrm{behind}(i,x)-1}+x=s\) である \(x\) について考えると \(\mathrm{front}(i,x) \leq i'\) が必要です。逆にこれが満たされるなら \(dp_{\mathrm{behind}(i',x)-1}+x \geq dp_{i}+x \geq s+1\) が成り立ちます。 よって \(dp_{i'}=s+1\) を満たす最小の \(i'\) は\(dp_{\mathrm{behind}(i,x)-1}+x=s\) を満たす \(x\) に対する \(\mathrm{front}(i,x)\) の最大値です。

よって以下のようなアルゴリズムで \(L\) を求めることができます。

1. \(L=0,\ S_x=x-1\) で初期化する。
2. \(s=0,\ 1,\ \dots,\ S-1\) の順に以下を行う。
   • \(S_{x}=s\) を満たす \(x\) について、\(L'=\mathrm{front}(L,x)\) とする。 \(L < i \le L'\) を満たす \(i\) に対し、 \(S_{A_i}\leftarrow dp_{\mathrm{behind}(L',A_i)-1}+A_i\) と更新し、 \(L\leftarrow L'\) と更新する。

この求め方でうれしい点として、 \(S_x=s\) となった場合 \(S_x\) は \(x\) だけ増加するので 2 の処理が行われるのは \(O(\sum_{x=1}^{S}\frac{S}{x})=O(S\log S)\) 回と少ないことがあげられます。しかし \(L\) の更新の際、各 \(x\) に対する \(S_x=dp_{\mathrm{behind}(L,x)-1}+x\) についても更新しなければならないのがネックになっています。

---

[3] 更新を遅延させる

そこで \(L\) を更新した際、各 \(x\) に対する\(dp_{\mathrm{behind}(L,x)-1}+x\) については正しい値に更新せず、\(S_x=s\) となったときに正しい値に更新します。すなわち、以下のようなアルゴリズムで \(L\) を求めることにします。

1. \(L=0,\ T_{x}=x-1\ (1\leq x \le S)\) で初期化する。
2. \(s=0,\ 1,\ \dots,\ S-1\) の順に以下を行う。
   • \(T_x=s\) を満たす \(x\) について、\(T_x \leftarrow dp_{\mathrm{behind}(L,x)-1}+x\) とする。その後、 \(T_x=s\) の場合は \(L \leftarrow \mathrm{front}(L,x)\) と更新し、\(T_x\leftarrow s+x\) と更新する。

この求め方だと \(T_x\) の更新による問題は解消しましたが、2 の処理が行われる回数についてはどうでしょうか？

実は \(T_x=s\) となったことが \(2\) 回あった後、更新後の \(T_x\) は \(x\) 以上増加しています。

証明

\(T_x\leftarrow dp_{\mathrm{behind}(L,x)-1}+x\) と更新した後、 \(T_x=s\) であった場合は明らかに \(x\) 以上増加するので、\(s < T_x\) となったことが \(2\) 連続であったケースを考えます。

\(1\) 回目の更新での（更新前の） \(L,\ s\) を \(L_1,\ s_1\) 、\(2\) 回目の更新での \(L,\ s\) を \(L_2,\ s_2\) とします。\(2\) 回目の更新で \(T_x\) を正しい値に更新した結果、 \(s < T_x\) となっているので \(s_2=dp_{\mathrm{behind}(L_1,x)-1}+x < dp_{\mathrm{behind}(L_2,x)-1}+x\) であり、 \(L_1 < \mathrm{behind}(L_2,x)\) が成り立ちます。よって \(dp_{\mathrm{behind}(L_2,x)-1}+x \geq dp_{L_1}+x=s_1+x\) であり、\(T_x\) は \(x\) 以上増加しています。

よって 2 の処理が行われる回数はこの求め方でも \(O(\sum_{x=1}^{S}\frac{S}{x})=O(S\log S)\) 回です。

以上より上記のアルゴリズムを用いることで \(O(N+S\log S(\log S + \log N))\) で条件を満たす最小の \(L\) を求めることができています。