更新クエリがない場合、この問題は以下のような手順で解くことができます。

1. \(N\) 日目に行う意味があるのは、\(D _ i = N\) である仕事だけである。そのうち \(P_i\) が最大のものを行うのが最適である。もし該当する仕事が無ければ \(N\) 日目には仕事を行わない。
2. \(N-1\) 日目に行う意味があるのは、先ほど選ばなかった仕事と、\(D_i=N-1\) である仕事である。そのうち \(P_i\) が最大のものを行うのが最適である。もし該当する仕事が無ければ \(N-1\) 日目には仕事を行わない。
3. \(N-2\) 日目以降についても同様

これは優先度付きキュー (priority queue) を用いることで高速にシミュレートできます。

更新クエリを処理するためには、優先度付きキューに対する一連の操作のうち一部が変化するという状況に対処する必要があります。データ構造に対する操作列の一部を変更することを効率的に行うデータ構造は retroactive データ構造と呼ばれており、様々な研究がおこなわれています。retroactive データ構造を初めて提案した論文 [1] において、優先度付きキューを retroactive にする手法が提案されています。より詳細には、以下の操作が可能です。

• 操作列の指定した場所に、\(\mathtt{push(x)}\) または \(\mathtt{pop}\) の操作を挿入し、全ての操作が終了した際のキューの中身の変化を出力する。時間計算量 \(\Theta(\log m)\)
• 操作列の指定した操作を削除し、全ての操作が終了した際のキューの中身の変化を出力する。時間計算量 \(\Theta(\log m)\)

ここで、\(m\) は操作列全体の長さです。すぐに分かる通り、最後までキューに残る値の補集合、すなわち途中で pop された値の集合の変化を管理することもできます。これで本問題を時間計算量 \(\Theta ((N + Q) \log N)\) で解くことができます。

実装例

https://atcoder.jp/contests/abc363/submissions/55828915 (実装の簡略化のため時間計算量が\(\Theta ((N + Q) \log (N + Q))\) になっています)

参考文献

[1] Demaine, E. D., Iacono, J., & Langerman, S. (2007). Retroactive data structures. ACM Transactions on Algorithms (TALG), 3(2), 13-es.