\(f(x)\) を \(L = 0, R = x\) と変更したときの答えとします。するとこの問題の答えは \(f(R) - f(L - 1)\) と表せます。よって、\(f(x)\) がどのような値になるかがわかれば良いです。

\(2N\) 回の操作に対して、長さ \(2N\) の数の組の列 \(((a_{1}, b_{1}), \dots , (a_{2N}, b_{2N}))\) を以下のように定義します。

• \(i\) 回目の操作までに行った行動 \(1\) の回数が \(a_{i}\) 回、\(i\) 回目の操作までに行った行動 \(2\) の回数が \(b_{i}\) 回

このとき、最終的な \(C\) について以下が成り立ちます。

• \(\displaystyle C = \max_{1\leq i\leq 2N}\left(\sum_{s = 1}^{a_{i}}A_{s} - \sum_{t = 1}^{b_{i}}B_{t}\right) - \left(\sum A - \sum B\right)\)

よって \(C\leq x\) であるときに限り、任意の整数 \(1\leq i\leq 2N\) について以下が成り立ちます。

• \(\left(\sum_{s = 1}^{a_{i}}A_{s} - \sum_{t = 1}^{b_{i}}B_{t}\right) \leq \left(\sum A - \sum B\right) + x\)

上記の条件に加え、\(a_{i}\geq b_{i}\) が任意の整数 \(1\leq i\leq 2N\) に対して成り立つような操作列の場合の数は、動的計画法を用いて時間計算量 \(O(N^{2})\) で求めることができます。

よって、この問題の制約下では十分高速に \(f(x)\) を求めることができるため、本問題も十分高速に解を求めることができます。

実装例

実装例 C++

実装例 pypy

補足

また、yosupo judge のとある問題に帰着できていることを踏まえれば、\(O(N\log^{2}(N))\) で \(f(x)\) を求めることもできます。