Original proposer: vwxyz

It is optimal to write emails in descending order of \(B\). (Within the same \(B\), the order does not matter.)
We will prove this.
Suppose that it is optimal to write to companies \(P_1,P_2,\dots,P_N\), in this order.
Suppose \(B_{P_i} \lt B_{P_{i+1}}\) for some \(i\).
Let \(S=\sum_{j=1}^{i-1}{A_{P_j}}\).
Swapping \(P_i\) and \(P_{i+1}\) makes the time receiving the email from company \(P_i\) from \(S+A_{P_i}+B_{P_i}\) to \(S+A_{P_{i+1}}+A_{P_i}+B_{P_i}\),
and the time receiving the email from company \(P_{i+1}\) from \(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}}),\) so swapping them does not worsen the time required to receive all emails. We also see that, if \(B_{P_i}=B_{P_{i+1}}\), then swapping \(P_i\) and \(P_{i+1}\) does not affect the time required. Hence, it is optimal to write emails in descending order of \(B\).

Prefetch the queries to enumerate all possible values for \(B_i\). Sort all \(B_i\), including those updated by queries, in descending order.
The current state of the companies can be maintained in a segment tree by storing the following two parameters on each node:

• the sum of \(A\)
• the time required to receive all emails

Prepare a segment tree of length equal to the number of enumerated values of \(B_i\) (allowing duplicates).
Every time \(B_i\) is updated, revert the node for the original \(B_i\) to the identity element, and store the updated information onto the node for the new \(B_i\).
The total time complexity is \(O((N+Q)\log{N+Q})\).