部分点解法 の \(B_i,C_i\) たちが求まっているものとします。また記号 \(x_0,\dots,x_{M-1}\) を同じ意味で用います。

非負整数 \(X\) について、次のようなアルゴリズムを考えます。\(x_0 = \min(X, B_0)\) とし、残りの \(x_1,\dots,x_{M-1}\) について最適な値を計算しています。

orig_X = X
# x_0, ..., x_{M-2}
for i in range(0, M-1):
    x[i] = min(X, B[i])
    X = C[i+1] - X
# x_{M-1}
x[M-1] = min(X, B[M-1], C[0] - orig_X)

明らかに、\(x_0,\dots,x_{M-1}\) は \(X\) に対して折れ線（区分線形な連続関数）になります。 またその総和 \(\sum x\) も同様です。

---

これから行う説明は、上のコードの書き方、つまり \(\min(X, B_i)\) や \(C_{i+1}-X\) の計算のタイミングに強く依存しています。 タイミングが異なっても似たような解法は成立するはずですが、細部がずれることに注意してください。

---

\(i=0,\dots,M-2\) のループ中で、\(X\) は \(C_{i+1}-\min(X, B_i)\) へと変化します。 そこで \(f_i(X):=C_{i+1}-\min(X, B_i)\) とします。これは非負整数から非負整数への折れ線です。

\(f\) のような折れ線をいくつか合成したものは、傾きが順に \(0,\pm 1,0\) であるような折れ線になります。 奇数回合成していれば真ん中の傾きは \(-1\)、偶数回であれば \(+1\) です。 またいくつかの区間の幅が \(0\) になることもあります。

折れ線 \(f_i\circ f_{i-1}\circ\dots\circ f_0\) について、三つの区間をそれぞれ \([0,\ell_i],[\ell_i,r_i],[r_i,\infty)\) とします。 また真ん中の区間の傾きを \(d_i\in\{+1,-1\}\) とします。 \(\ell_i=r_i\) となる場合についてはいったん無視します。

次に \(\sum_{j=0}^i x_j\) を考えます。 より正確には、\(g_i(X):=\sum_{j=0}^i\min((f_{j-1}\circ f_{j-2}\circ\dots\circ f_0)(X), B_j)\) がどのような折れ線になるかを考えます。 \(x_i\) を計算するタイミングがループの途中なので、このような複雑な式になっています。

実は、\(g_i\) は次のような性質を持ちます。

• \(d_i=+1\) のとき、区間 \([0,\ell_i]\) で傾き \(+1\)、区間 \([\ell_i,\infty)\) で傾き \(0\) である
• \(d_i=-1\) のとき、区間 \([0,r_i]\) で傾き \(+1\)、区間 \([r_i,\infty)\) で傾き \(0\) である

ここで、先ほど無視した \(\ell_i=r_i\) となる場合については、その値を上の性質が満たされるように定めることとします。 \(d_i\) については \(\pm 1\) のどちらでもよいです。

---

これで必要な折れ線が常に定数個のパラメータで表現できることが分かりました。あとはこの合成を実装すればセグメント木に乗り、\(B_i\) や \(C_i\) の更新が行えるようになります。 ここで合成とは、折れ線のペア \((f_\ell,g_\ell)\) と \((f_r,g_r)\) から \((f_r\circ f_\ell,\;g_\ell+(g_r\circ f_\ell))\) を求める操作です。

折れ線のペア \((f,g)\) を表現するパラメータとしては、例えば以下の五つの組を用いることができます。

• \(f\) について、傾きが切り替わるタイミングを表す \(\ell,r\)（ただし \(0\le\ell\le r\)）
• \(f\) の区間 \([\ell,r]\) における傾き \(d\)（ただし \(d\in\{+1,-1\}\)）
• \(a:=f(\ell)\)
• \(g\) について、傾きが切り替わるタイミングにおける値 \(v\)（つまり \(d=+1\) なら \(v=g(\ell)\)、\(d=-1\) なら \(v=g(r)\)）

例として、\(f(X)=C-\min(X, B),g(X)=\min(X,B)\) なら \((\ell,r,d,a,v)=(0,B,-1,C,B)\) です。

合成する際は \(\ell,r\) さえ計算できれば残りの値は直ちに求まります。\(f_\ell\) の真ん中の区間を延長した線形関数 \(h(X):=a_\ell+d_\ell(X-\ell_\ell)\) について、\(L:=h^{-1}(\ell_r),R:=h^{-1}(r_r)\) としたとき、合成後の \((\ell,r)\) はそれぞれ

• \(\ell=\operatorname{clamp}(\min(L,R),\ell_\ell,r_\ell)\)
• \(r=\operatorname{clamp}(\max(L,R),\ell_\ell,r_\ell)\)

となります。ここで \(\operatorname{clamp}(v,l,r):=\min(\max(v,l),r)\) です。

---

これで部分点解法でいう関数 \(g\) の値が定数時間で求められるようになりました。あとは \(g(0)\) と \(g(B_0)\) から 最適な \(X\) を求めてもよいですが、\(g\) は傾きが順に \(+1,0,-1\) であるような折れ線なので、傾きに関する二分探索や値に関する三分探索を行うという方法もあります。

実装例