目的関数を観察する

\(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) を高速に求めるために、まず \(Ax + By\) がどんな関数であるかを観察します。

図に表してみると、ベクトル \((A, B)\) の方向へ行けば行くほど値が大きくなることが分かります。これは、\(Ax + By\) がベクトル \((A, B)\) とベクトル \((x, y)\) の内積であることからも分かります。したがって、\(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) はベクトル \((A, B)\) の方向へ最も移動した点で最大値を取ります。

点の追加がない場合

点の追加がなく、\(S\) に \(N\) 個の点が含まれていて、\(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) を求めるクエリがたくさん与えられる場合を考えます。

上の考察より、\(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) は \(S\) の外側、すなわち、\(S\) の凸包上の点以外では最大値を取れないことがわかります。また、\(S\) の凸包上の点を順番にならべると目的関数に単調性があります。そのため、前計算として \(O(N \log N)\) 時間で \(S\) の凸包を取った後、三分探索や黄金分割探索などを使ってクエリあたり \(O(\log N)\) 時間で最大値を求めることができます。

点の追加がある場合

さて、元の問題を考えましょう。点の追加があるので、\(S\) の凸包を動的に管理する必要があります。これは、凸包上の点を順番に並べた列を平衡二分探索木で管理すれば、クエリあたり \(O(\log Q)\) 時間で点の追加を処理することができるので、全体で \(O(Q \log Q)\) 時間でこの問題を解くことができます。

しかし、この方法には問題があります。多くの言語の標準ライブラリにある平衡二分探索木では機能不足で、高機能な平衡二分探索木を用意する必要があるのです。

__gnu_pbds::tree のように、\(n\) 番目の要素にアクセスする機能がある平衡二分探索木を使えば \(O(Q (\log Q)^2)\) にできるので、これで解くのも良いでしょう。

区間クエリと捉える

もう少し別の方法を探してみましょう。

\(i\) 番目のクエリを、点 \(1\) から点 \(i\) までの区間に対するクエリだと捉えてみましょう。区間に対するクエリを高速に求める方法といえば、セグメント木です。セグメント木の各区間に対して、その区間の点の凸包を前計算しておけば、\(\displaystyle \max_{(x,y) \in S}\{Ax + By\}\) を求めるときには、\(O(\log Q)\) 個の凸包で最大値を計算してそれらの \(\max\) を取れば良いので、\(O(Q (\log Q)^2)\) 時間でこの問題を解くことができます。

おまけ問題 : 平衡二分探索木を使わずに、\(O(Q \log Q)\) 時間にしてください。

実装例 (C++)

実装例 (Python)