（0-indexed で表記します。）

バウンディングボックスの面積は \((X_{max}-X_{min})(Y_{max}-Y_{min})\) のような式になります。

\(Y\) の各 prefix についての \(Y_{max}-Y_{min}\) を \(W_i\) とします。

同様に、\(X\) の各 prefix の \(X_{max}-X_{min}\) を \(A_i\) とします。

\(f(X)\) の最小値

\(f(X)\) が \(R\) 以下であるような \(X\) についての \(A\) が満たすべき条件は以下の通りです。

• \(A_0 = 0\)
• \(i \le A_i \le N-1\)
• \(A_i \le A_{i+1}\)
• \(W_iA_i \bmod M \le R\)

\(f(X)\) の最小値は以下のような dp で求めることが出来ます。

• \(dp[i][j]=\) \(A_i\) まで決めて \(A_i=j\) にしたときの \(W_iA_i \bmod M\) の最小値

愚直に計算すると \(O(N^3)\) ですが、累積 min などで容易に \(O(N^2)\) に計算量を落とすことが出来ます。

数え上げ

ある \(A\) に対応する \(X\) の個数は、\(X_0=0\) と固定して \(X_1,X_2,\dots,X_{N-1}\) を順に自由に決めた後、全体から \(min(X)\) を引くという手順を考えると、以下のように求めることが出来ます。

• \(i=1,2,\dots,N-1\) についての以下の値の総積を求める
  • \(A_{i-1} \lt A_i\) のとき：\(2\)（最小か最大のどちらを更新するか）
  • \(A_{i-1} = A_i\) のとき：\((j-i+1)\)（min～maxの間の余りの個数）

これを踏まえると最小値を求めるときと同様の dp を行うことが出来ます。

• \(dp[i][j] = A_i\) まで決めて \(A_i=j\) であるようなものについての上記の値の積の和

愚直に計算すると \(O(N^3)\) ですが、累積和などで容易に \(O(N^2)\) に計算量を落とすことが出来ます。

余談

最小値は二分探索でも求めることが出来ますが、判定関数として \(\bmod P\) での数え上げ関数を使用すると個数が \(P\) の倍数になるケースで壊れるので注意してください。

これをテーマにした問題が D 問題です。D 問題の解法に関する情報をテストケースから得られないようにするために、個数が \(P\) の倍数になるケースは以下の方法で生成しています。（これが mod が 固定でない理由です。）

1. \(M,Y\) をランダムに生成し、答えを多倍長整数で計算する
2. 答えの素因数に含まれる制約範囲内の素数を探し、\(P\) とする