「操作を高々 \(k\) 回行ったときの嬉しさの最大値」の代わりに「嬉しさを \(k\) 以上にするための操作回数の最小値」を求めることにします．

分割統治法で求めます． \(f(l,r,a,b)\) を， \(S_lS_{l+1}\dots S_r\) に対し左端を \(a\) ，右端を \(b\) にしたときの答とすると， \(f(l,r,a,b)\) は下凸なので， \(x=\text{S},\text{R}\) に対し \(f(l,\lfloor\frac{l+r}{2}\rfloor,a,x),f(\lfloor\frac{l+r}{2}\rfloor,r,x,b)\) を求め， min-plus convolution をすれば得られます．

計算量は \(O(N\log N)\) であり，多少の定数倍がつきます．

下凸性の証明はいつか書きます．