最后一分钟场切。
首先我们知道答案按 $B$ 降序排序一定最优。证明？扔个官方证明吧。
:::success[证明]
假设按顺序 $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+1}}+B_{P_{i+1}}$ 变为 $S+A_{P_{i+1}}+A_{P_i}+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$ 的降序写信是最优的。
:::
设最优顺序为 $p_1,p_2,p_3,\ldots,p_n$。
现在考虑对于一个询问，答案即
$$\max_{i=1}^n [(\sum_{j=1}^{i-1}B_{p_j}) + A_{p_i}]$$发现式子里竟然有区间最大值！同时我们又要进行单点修改，不妨使用线段树。
考虑节点维护以下信息：
-
$maxv$：区间答案
-
$sum$：区间元素和
两个节点信息合并：
$$sum=sum_L+sum_R$$$$maxv=\max(maxv_L,sum_L+maxv_R)$$由于 $B_i$ 比较大，还需要离散化。但这引入了一个新问题：由于修改 2 可能导致 $B_i$ 在排序后的数组中的位置移动，我们还需要在离散化的时候顺便把操作 2 可能用到的位置也预留下来。
:::success[code]
使用了 AtCoder Library。
|
|
:::