この問題は様々な解法が考えられると思います。(マトロイドを利用するのも一案です。)
本解説では、問題を費用流の形で定式化して高速化するという方針で解く方法を解説しています。

Segment Tree 分割統治を利用した前処理

まずはじめに、この問題のような オフラインクエリ(クエリがあらかじめ既知) の問題では、「Segment Tree 分割統治」と呼ばれるテクニックを適用すれば要求されているクエリを単純にすることが出来ます。

• このテクニックは典型的であるにも拘らず日本では特に名前がついていないようなので、 OI Wiki を参考にして命名しました。

この問題で要求されているクエリを言い換えると次のようになります。

仕事に関する集合があり、はじめ空である。次のクエリを処理

• 集合に新たに仕事を \(1\) 個追加する (追加クエリ)
• 集合から仕事を \(1\) 個選び削除する (削除クエリ)
• 小問題の答えを出力する

つまり簡単に言うと、データ構造への追加クエリと削除クエリを要求している問題となっています。
一般に集合を管理するデータ構造において、削除クエリの処理は、そのデータ構造がよほど単純でない限りは困難である場合が多いです。例えば Union-Find は削除クエリをサポートしていません。
Segment Tree 分割統治を利用すると、この削除クエリを undo クエリに変えることができます。つまり次の通りです。

仕事に関する集合があり、はじめ空である。次のクエリを処理

• 集合に新たに仕事を \(1\) 個追加する (追加クエリ)
• 集合から 直前に追加した仕事 を \(1\) 個削除する (undo クエリ)
• 小問題の答えを出力する

undo クエリは削除クエリと違って、直前の状態との差異を stack で保持するなどの方法を利用することで計算量を悪化させずに処理することができる場合が多いです。例えば Union-Find はその手法を取ることで容易に undo クエリに対応できます。
よって、Segment Tree 分割統治を用いれば、追加・削除クエリの 2 種類が必要だったものが追加クエリだけ処理できれば良いことになり、問題によっては大幅な単純化につながります。

Segment Tree 分割統治の手法を簡単に説明します。
まず、時刻を管理するための Segment Tree を用意します。ここでの時刻とは、最初のクエリを処理するタイミングを時刻 \(0\)、次のクエリを処理するタイミングを時刻 \(1\)、のように割り当てたものを言います。Segment Tree の各ノードは、要素を管理する vector を保持しています。
次に、前処理を適切に行うことで、集合に追加する各要素について、その要素が存在する期間 \([l, r)\) を計算できます。そして、Segment Tree の区間更新を行う手順と同様に、\([l, r)\) に対応するノードにその要素を追加します。
追加する処理が終わったら、Segment Tree の根から DFS を開始します。DFS の内部では、各ノードに入るにノードの vector に含まれる要素を集合に追加して、ノードから出る時に追加した分を undo で取り消します。この DFS において、\(i\) 番目の葉に到達したときの集合の状態が \(i\) 番目のクエリを処理したタイミングでの集合の状態と一致しています。

• ei1333 さんの記事のスライドの P.52 以降 に Union-Find を具体例に挙げた図つきの説明が載っているので、詳しくはそちらを参照してください。

クエリの個数を \(Q\)、時刻の最大値を \(T\) 、追加クエリと undo クエリの計算量を \(\mathrm{O}(f(n))\) とした時、全体の計算量は \(\mathrm{O}(Q \log T f(n))\) になります。

費用流による定式化

さて、Segment Tree 分割統治を適用することで、次の問題を解ければよいことになりました。

仕事に関する集合があり、はじめ空である。次のクエリを \(\mathrm{O}((N + Q) \log Q)\) 回処理

• 集合に新たに仕事を \(1\) 個追加する
• 集合から直前に追加した仕事 を \(1\) 個削除する
• 小問題の答えを出力する

ここで、undo クエリは前述の通り適切な処理をすれば追加クエリと同じ計算量で処理できるので一旦無視します。また、集合に仕事を追加するごとに最適解を計算し直すことにすると、クエリは次の 1 種類で済むことになります。

仕事に関する集合があり、はじめ空である。次のクエリを \(\mathrm{O}((N + Q) \log Q)\) 回処理

• 集合に新たに仕事を \(1\) 個追加する。そして、小問題の答えを計算する

以降ではこの問題を解くことを考えます。
問題を費用流の形で記述すると次のようになります。

\(S, A_1, \dots, A_N, B_1, \dots, B_N, T\) というラベルのついた \(2N+2\) 個の頂点からなるグラフがある。
グラフの辺は以下のように張られている。

• \(j \leq D_i\) を満たす \((i, j)\) の組について \(A_i \to B_j\) に容量 \(1\) 、コスト \(0\) の辺
• \(B_j \to T\) に容量 \(1\) 、コスト \(0\) の辺
• \(T \to S\) に容量 \(\infty\) 、コスト \(0\) の辺

そして、クエリは次のように表現できます。

• 仕事 \(i\) を追加する時、\(S \to A_i\) に容量 \(1\) 、コスト \(-P_i\) の辺を追加して、その時の最小費用循環流の答えを \(-1\) 倍したものを計算する

以降ではこの言い換えをした問題を考えます。
クエリを処理する際に、常に最適な費用流の残余グラフを保持することを考えます。(すなわち、残余グラフに負閉路が存在しない状態を維持します。) この時、クエリで \(S \to A_i\) に辺を追加したときの残余グラフの挙動を考えると、実は次の事実が言えます。

補題

クエリで辺を追加した後に「負閉路が存在すれば、コストが最小の負閉路を消去する」という操作を高々 \(1\) 回行うと、残余グラフに負閉路が無くなる。

(証明)辺を追加しても負閉路が生じない場合は操作を行わなくても最適性が維持されているので何もしなくても良い。新たに負閉路が生じる場合を考える。
元の残余グラフに負閉路が存在しないことから、新たに生じた負閉路は追加した辺を使用している。 (よって負閉路を消去する際に流すフローの流量は \(1\) である。) このような閉路のうち最もコストが小さい負閉路を \(C\) と呼ぶ。また、辺を追加する前のグラフを \(G\)、辺を追加して \(C\) に流量 \(1\) のフローを流した後のグラフを \(G'\) と呼ぶ。\(G'\) が負閉路を持たないことを証明すればよい。

\(G'\) に負閉路が含まれると仮定して、その負閉路を \(C'\) とする。
新たに追加した辺の流量は \(1\) なので \(C'\) は新たに追加した辺自身を含まない。また \(C'\) の辺が \(G\) に含まれる辺のみから構成されるとすると \(G\) の最適性に反する。よって、\(C\) にフローを流したことによって発生した逆辺を含むことがわかる。

ここで \(C\) に登場する辺を各辺流量 \(1\) の分だけ取り出したものと、\(C'\) に登場する辺を同様に各辺流量 \(1\) の分だけ取り出したものを合成してできるグラフを考える。すると、そのグラフは次の \(3\) 種類の辺集合によって構成されることがわかる。

1. \(C\) に含まれる辺と、その逆辺であって \(C'\) に含まれるもののペアが \(1\) 個以上
2. \(G\) に含まれる閉路が \(0\) 個以上
3. 新たに追加した辺を含み、それ以外の辺は \(G\) に含まれる辺のみからなる閉路が \(0\) 個または \(1\) 個

ここでこのグラフに登場する辺のコストの総和を考えると、 \(C, C'\) はともに負閉路なので負であることが確認できる。 一方、1. に含まれる辺のコストの総和は \(0\) であり、また、2. に含まれる閉路は \(G\) に存在する閉路なのでコストは 0 以上である。 よって 3. に該当する閉路が存在しない場合は 1. 2. 3. のコストの総和が非負になるため矛盾して不適である。 また、存在する場合も、その閉路を \(C''\) として、閉路 \(c\) のコストを \(w(c)\) のように表すと

\[\begin{aligned} w(C) + w(C') &= (1. の寄与) + (2. の寄与) + (3. の寄与) \geq w(C'') \end{aligned}\]

\[\begin{aligned} w(C) \geq w(C'') - w(C') > w(C'') \end{aligned}\]

となり 、\(C''\) のコストが \(C\) よりも小さいことが証明できるが、これは \(C\) をコスト最小の負閉路として選んできたことと矛盾する。
以上より \(C'\) が存在すると仮定して矛盾を導けたので、\(G'\) に負閉路は存在せず、最適な費用流の残余グラフとなっていることが言える。(証明終わり)

さて、この解説内で最も難しいであろう部分を乗り越えることが出来ましたが(筆者はこの証明に苦労しました)、費用流への言い換えや補題自体はそのままでは高速化に役立ちません。(コスト最大の負閉路の発見は一般のグラフでは NP 困難であることが知られています) そこで、グラフの性質を利用して費用流のシミュレーションを高速化することを考えていきます。

仕事の集合を利用した費用流のシミュレーション

まず、費用流をそのまま扱っても高速化は望めないので、費用流に対する操作を仕事の集合に対する操作に言い換えてみます。
まず、構築したグラフは二部グラフマッチングをフローとして表現した形を取っています。そのため、\(S \to A_i\) にフローが流れている \(i\) の集合が小問題において期限内に終わらせた仕事の集合と一致することは明らかです。よって、\(1\) つの残余グラフに対して、小問題において期限内に終わらせた仕事の集合を \(1\) 個対応させることが出来ます。以降ではこの期限内に終わらせた仕事の集合を \(X\) と呼び、残余グラフの代わりに \(X\) を保持することにします。つまり、クエリ形式で表現すると次のようになります。

仕事に関する集合があり、はじめ空である。
また、現在の仕事の集合に対して、小問題を解いた時に、最適解において期限内に終わらせる仕事の集合を \(X\) とする。
次のクエリを \(\mathrm{O}((N + Q) \log Q)\) 回処理

• 集合に新たに仕事 \(i\) を追加して、対応する \(X\) も更新する。そして、\(X\) に含まれる仕事の報酬の総和を出力

次は「対応する \(X\) も更新する」という部分をより詳しく考えてみます。
まず、負閉路の消去が \(X\) を用いてどのように表現できるかを考えてみましょう。残余グラフに負閉路が存在する時、負閉路は次の \(2\) 通りのどちらかの形をしています。

• \(S \to A_i \to B_* \to A_* \to \dots \to B_* \to T \to S\)
• \(S \to A_i \to B_* \to A_* \to \dots \to B_* \to A_j \to S\)

この \(2\) つの閉路を仕事の集合に対する操作に言い換えると次のようになります。

• \(X\) に仕事 \(i\) を追加する
• \(X\) から仕事 \(j\) を取り除いて、仕事 \(i\) を追加する

逆に、この \(2\) つの操作ができるときに、それぞれ残余グラフに対応する負閉路が存在することも証明できます。よって、\(2\) 種類の操作がそれぞれ可能であることは \(2\) 種類の負閉路がそれぞれ存在することと等価です。
(証明の概要) 前者同士が対応することを証明する。(後者も同様に証明できる) \(X\) に対応する残余グラフと \(X + \lbrace i \rbrace\) に対応する残余グラフを合成して逆辺同士を打ち消し合うと「\(S \to A_i \to B_* \to \dots \to B_* \to T \to S\)」+ 「\(0\) 個以上のコスト \(0\) の閉路」からなることが確認できて、かつ前者は \(G\) に含まれる辺からなることも言える。(証明終わり)

以上より、負閉路およびその消去を仕事の集合に対する操作に言い換えることが出来ました。
次は、残余グラフを更新する時の処理を \(X\) に対する操作に言い換えてみましょう。補題より、費用流において残余グラフを更新する操作は

• 負閉路が存在すれば、コストが最小の負閉路を消去する

という処理でよいことがわかっています。この「コストが最小」という部分を詳しく言い換えると次のようになります。

• 「\(S \to A_i \to B_* \to \dots \to B_* \to T \to S\)」という形の負閉路があれば流す。
• そうでない場合、「\(S \to A_i \to B_* \to \dots \to B_* \to A_j \to S\)」という負閉路が存在すれば、そのうちコストが最小の負閉路に流す。
• そうでない場合、何もしない。

これを仕事の集合に対する操作に言い換えると次のようになります。

• \(X\) に仕事 \(i\) を追加できる場合は追加する。
• そうでない場合、「\(P_i \gt P_j\)」 かつ「\(X\) から仕事 \(j\) を取り除けば仕事 \(i\) を追加できる」\(j\) が存在すれば、そのような \(j\) のうち \(P_j\) が最小のものを選び、\(X\) から仕事 \(j\) を取り除き仕事 \(i\) を追加する。
• そうでない場合は何もしない。

以上の議論により、費用流による定式化を仕事の集合に対する操作に言い換えることが出来ました。
さて、かなり操作が具体的になってきました。解けばよい問題をクエリ形式で表現すると次のようになります。

仕事に関する集合があり、はじめ空である。
また、現在の仕事の集合に対して、小問題を解いた時に、最適解において期限内に終わらせる仕事の集合を \(X\) とする。
次の一連のクエリを \(\mathrm{O}((N + Q) \log Q)\) 回処理

• 集合に新たに仕事 \(i\) を追加する。
• \(X\) に対して次の操作を行う。
  • \(X\) に仕事 \(i\) を追加できる場合は追加する。
  • そうでない場合、「\(P_i \gt P_j\)」 かつ「\(X\) から仕事 \(j\) を取り除けば仕事 \(i\) を追加できる」\(j\) が存在すれば、そのような \(j\) のうち \(P_j\) が最小のものを選び、\(X\) から仕事 \(j\) を取り除き仕事 \(i\) を追加する。
  • そうでない場合は何もしない。
• \(X\) に含まれる仕事の報酬の総和を出力する。

ここまで言い換えればあとはラストスパートです。

Hall の結婚定理の適用による高速化

さて、上記のクエリを処理するために、次のようなデータ構造を構成することにしましょう。

仕事の集合を \(X\) とする。 小問題において \(X\) に含まれる仕事全てを期限内に終わらせられる時、\(X\) が valid であると呼ぶ。 次のクエリを処理できるデータ構造を構成せよ。

• \(X\) に仕事 \(i\) を追加する
• \(X\) から仕事 \(i\) を取り除く
• \(X\) が valid であるかを判定する
• \(X\) が valid でない場合、「\(X\) から仕事 \(i\) を取り除けば \(X\) が valid になる」ような \(i\) のうち \(P_i\) 最小のものを発見する

クエリ全種類を一度に処理しようとすると大変なので、まずは \(1\) 番目と \(3\) 番目のクエリだけを考えてみましょう。すなわち次の \(2\) 種類です。

• \(X\) に仕事 \(i\) を追加する
• \(X\) が valid であるかを判定する

この \(2\) 種類のクエリを処理するために、仕事に関する情報を工夫して持つことを考えましょう。 小問題の設定を思い出すと、\(X\) が valid であることは二部グラフのマッチングで表現できます。すなわち次の通りです。

\(X\) に含まれる仕事に対応する頂点集合を \(U\) 、日付に対応する頂点集合を \(V\) とする。
\(u \in U, v \in V\) について、日付 \(v\) が仕事 \(u\) の期限内であるときに \(u \to v\) に辺を貼る。 この時、\(X\) が valid である必要十分条件は \(U\) をカバーするマッチングが存在することである。

二部グラフの片方の頂点をすべてカバーするマッチングの存在の有無を判定する問題と言えば、Hall の結婚定理の出番です。この条件を Hall の結婚定理を用いて上手く書き換えてみましょう。

\(A \subseteq U\) に対して \(\Gamma(A)\) を \(A\) と辺でつながっている頂点の集合とします。Hall の結婚定理は次の式で表せます。

Hall の結婚定理

\(U\) の頂点をカバーするマッチングが存在することは次の条件式と同値：

\[\forall A \subseteq U, |A| \leq |\Gamma(A)|\]

この式は \(U\) 側の集合に関する条件ですが、この条件式を変形することで \(V\) 側の集合に関する条件式を導出することが出来ます。(証明略。式の意味を解釈すれば理解できると思います)

Hall の結婚定理を式変形したもの

\(U\) の頂点をカバーするマッチングが存在することは次の条件式と同値：

\[\forall B \subseteq V, |\lbrace u \vert u \in U, \Gamma(u) \subseteq B \rbrace| \leq |B|\]

このように \(V\) 側の集合に関する条件式にすることで、今回の問題の特性を生かすことが出来るようになります。
\(I_n\) を日付 \(1\), 日付 \(2\), \(\dots\), 日付 \(n\) の集合に対応する \(V\) の部分集合とします。各仕事 \(i\) について、対応する頂点から \(I_{D_i}\) へ含まれる頂点へ辺が伸びています。この事実から、上記の条件式において \(V\) として考える必要があるのが \(I_1, I_2, \dots, I_N\) だけで良いことが証明できます。(証明略)

\(B = I_n\) の時の条件式を整理すると次のようになります。

\[ \begin{aligned} &|\lbrace u \vert u \in U, \Gamma(u) \subseteq I_n \rbrace| \leq |I_n| \\ \iff &|\lbrace u \vert u \in U, D_u \leq n \rbrace| \leq n \\ \iff &n - |\lbrace u \vert u \in U, D_u \leq n \rbrace| \geq 0 \end{aligned} \]

以上の事実を踏まえると、クエリを処理するデータ構造を次のように構成できます。

\[f(n) = n - |\lbrace u \vert u \in U, D_u \leq n \rbrace|\]

とおく。\(X\) の代わりに \(f(1), f(2), \dots, f(n)\) を区間加算・区間 min を処理できる遅延セグメント木を用いて管理することにする。

• \(X\) に仕事 \(i\) を追加する時は \(f(D_i), f(D_i + 1), \dots, f(N)\) に \(-1\) を加算すればよい。
• \(X\) が valid であるという条件は \(f(1), f(2), \dots, f(N)\) が全て非負であるという条件と等しいので、 \(\min(f(1), f(2), \dots, f(N)) \geq 0\) かどうかを判定すればよい。

以上より、クエリが仕事の追加と valid かどうかの判定の \(2\) 種類の場合の問題を解くことが出来ました。
本質部分を説明したので以降の細かい説明は省略しますが、後回しした \(2\) 番目のクエリと \(4\) 番目のクエリも上手くやれば処理できます。簡単に説明すると、\(2\) 番目のクエリは \(1\) 番目のクエリと同様の方法で処理できて、\(4\) 番目のクエリは std::set や 1 点更新・区間 min Segment Tree を上手く併用すれば処理できます。また、いずれのクエリについても undo クエリを容易に実装できます。

以上より \(X\) を管理するデータ構造をクエリあたり \(\mathrm{O}(\log N)\) で構成することができました。よって、問題全体を \(\mathrm{O}((N + Q) \log Q \log N)\) で解くことが出来て、これは十分高速です。

Bonus

以上が想定解でしたが、実は筆者の手元には \(\mathrm{O}((N + Q) \log N)\) で全てのテストケースに対して正答を返すコードがあります。ここで歯に物が引っ掛かった言い方をしているのには理由があって、筆者がこの新しい解法に気づいたのがコンテスト前日の夜中で、正当性をきちんと証明する時間が無かったからです。そこで、次の問題を Bonus として置いて解説を終えたいと思います。

Bonus ：\(\mathrm{O}((N + Q) \log N)\) でこの問題を解いてください。