原案:vwxyz

\(B\) が大きい方から書いていく（\(B\) が同じ値ならばどの順に書いても変わらない）のが最適です。
これを証明します。
会社 \(P_1,P_2,\dots,P_N\) の順にメールを書くのが最適だとします。
ある \(i\) で、\(B_{P_i} \lt B_{P_{i+1}}\) と仮定します。
\(S=\sum_{j=1}^{i-1}{A_{P_j}}\) と置きます。
\(P_i\) と \(P_{i+1}\) を入れ替えると、
会社 \(P_i\) からのメールの返信時刻は \(S+A_{P_i}+B_{P_i}\) から \(S+A_{P_{i+1}}+A_{P_i}+B_{P_i}\) に変わります。
会社 \(P_{i+1}\) からのメールの返信時刻は \(S+A_{P_i}+A_{P_{i+1}}+B_{P_{i+1}}\) から \(S+A_{P_{i+1}}+B_{P_{i+1}}\) に変わります。
\(\max(S+A_{P_i}+B_{P_i},S+A_{P_i}+A_{P_{i+1}}+B_{P_{i+1}}) \\ =S+A_{P_i}+A_{P_{i+1}}+B_{P_{i+1}}\\ \gt \max(S+A_{P_{i+1}}+A_{P_i}+B_{P_i},S+A_{P_{i+1}}+B_{P_{i+1}})\) なので、損をしないことがわかります。 また、\(B_{P_i}=B_{P_{i+1}}\) ならば、\(P_i\) と \(P_{i+1}\) を入れ替えてもすべての返信を受け取り終える時刻は変わらないこともわかります。 よって、\(B\) が大きい方から書いていくことがわかります。

クエリを先読みして、出てくる \(B_i\) を列挙します。 クエリで \(B_i\) が変わるたびにそのときの \(B_i\) も加え、全体を降順に並べます。

• \(A\) の総和
• すべての返信を受け取り終える時刻

の \(2\) つを持たせれば各会社の情報はセグ木の乗せることができます。
列挙した \(B_i\) の（重複も許した）個数分の長さのセグ木を用意します。
\(B_i\) が変更されるたびに、元の \(B_i\) に対応するノードを単位元に戻し、新しい \(B_i\) に対応するノードに新しい情報を更新すればよいです。
計算量は全体で \(O((N+Q)\log{N+Q})\) です。