公式解説の補足を書きます。まずは公式解説を参照してください。

結局、直線 \(ax+b\) の追加と、ある \(x\) 座標で最大値の取得を処理するクエリの処理に帰着されます。 直線の追加は \(\Theta(N^2)\) 回、最大値の取得は \(\Theta(Q)\) 回行われるため、一般の Convex Hull Trick を用いると時間計算量は \(\Theta((N^2 + Q) \log(N))\) となります。 一方で公式解説の時間計算量は \(\mathrm{O}(N^2 + Q \log (N))\) となっています。これを達成するためには、単調性を用いた改善を行います。

追加する \(ax+b\) の \(b\) が単調増加になっており、更に最大値を取得する \(x\) は非負であることに着目します。 \(ax+b\) を追加する時、過去に \(a^{\prime} \leq a\) となる \(a^{\prime}x + b^{\prime}\) が追加されていた場合、これはもはや最大値を与え得ないので、削除して問題ありません。 したがって \(a\) が単調減少になるように直線群を管理すると、Convex Hull Trick において傾きが単調な場合に直線の追加を \(\rm{amortized}\ \mathrm{O}(1)\) で行うアルゴリズムとほとんど同一の処理を適用することが可能です。 最大値の取得は単調ではないので、単に \(\Theta(\log(N))\) のアルゴリズムを用います。