仕事を変化させずに \(1\) パターン計算する場合は、 \(k=N,\ldots ,2,1\) の順に、 \(k\) 日目に行える仕事を優先度付きキューに加えて \(1\) つ取り出すということを繰り返せば答えられます。

• 仕事の個数を \(N\)
• スケジュールの日数を \(M\)
• クエリの個数を \(Q\)

と置きなおします。また、 \(1\) 日に複数の仕事が追加されることを許すとします。

ここで仕事が \(1\) つ追加されたとします。報酬が大きければ期限内に実行されますが、その分ほかの仕事が後回しになり、また高々 \(1\) つの仕事が実行されなくなります。以降ではこの挙動の特性を暗黙に利用します。

クエリ分割統治を利用します。任意の問題を、 \(Q\) の値を変えずに、 \(N\) および \(M\) の値が \(O(Q)\) に収まるような同じ形式の問題に帰着できれば、クエリ分割統治が成立します。

以下で説明する方法で、変形にかかる計算量は \(O((N+M+Q)\log (N+M+Q))\) になるので、元の問題(ABC363G)全体の計算量は \(O((N+Q)(\log (N+Q))^2)\) です。

まず、クエリで変化しない仕事を次のように \(3\) つに分類します。

• 必ず実行される仕事 : クエリで変化する仕事を報酬 \(\infty\) とおき、変化前および各変化の後をすべて重複して追加してシミュレーションしたときに実行される仕事です。
• 実行され得ない仕事 : クエリで変化する仕事を無視してシミュレーションしたときに実行されない仕事です。
• それ以外の仕事

\(2\) つのシミュレーションで追加する仕事の個数の差は \(O(Q)\) なので、「それ以外の仕事」は \(O(Q)\) 個です。それ以外は、分割後の問題では無視できます。

次に、以下の考察のもと、スケジュールを \(O(Q)\) 日に圧縮します。

• 「必ず実行される仕事」のシミュレーションで仕事を行わなかった日は、分割後の問題でも使用しません。
• 仕事のスケジュールを具体的に考えたとき、「必ず実行される仕事」を実行する日を、「必ず実行される仕事」のシミュレーション通りに置き換えることで、他の仕事が遅れることはないようにできます。

以上より、もともとの問題を \(O((N+Q)(\log (N+Q))^2)\) 時間で解くことができます。

実装例 https://atcoder.jp/contests/abc363/submissions/55820688