ABC467F Email Scheduling Optimization

问题

ABC467F Email Scheduling Optimization
有 $N$ 封邮件，第 $i$ 封需要 $A_i$ 分钟编写，发送后再经过 $B_i$ 分钟收到回复。同一时间只能编写一封邮件，需要在每次单点修改某个 $A_i$ 或 $B_i$ 后，求最早收到全部回复的时间。

数据规模：$N,Q\le 10^5$，并且 $A_i,B_i\le 10^9$。

这是一个动态修改问题，不过先要解决静态情况下的最优发送顺序。假设当前已经花费 $T$ 分钟，接下来有两封邮件 $x,y$，并且 $B_x<B_y$。

若先写 $x$ 再写 $y$，两封邮件中较晚的回复时间一定是 $T+A_x+A_y+B_y$。若先写 $y$，两次回复时间分别为 $T+A_y+B_y$ 与 $T+A_y+A_x+B_x$，二者都不超过前一种顺序的最晚回复时间。

因此，相邻逆序对都可以交换而不使答案变差，最优顺序就是按照 $B_i$ 从大到小处理。排序后，答案是所有“当前前缀编写时间加当前邮件等待时间”的最大值。

不过修改 $B_i$ 会改变邮件所在位置，不能每次重新排序。可以预先收集初值与修改值并离散化，把线段树坐标设为从大到小排列的 $B$ 值。

对于一个连续值域区间，节点保存 sum 与 mx。sum 表示这段中所有邮件的总编写时间，mx 表示从时间 $0$ 开始按顺序处理这一段时，最晚收到回复的时间。

若左区间的 $B$ 更大，那么左侧必须先于右侧处理。父区间的总编写时间为 L.sum + R.sum，右区间的全部完成时间还要整体推迟 L.sum，所以有 mx = max(L.mx, L.sum + R.mx)。

▶

ABC467F 的有序摘要

struct Info {
    long long sum = 0;
    long long mx = -inf;
};

Info merge( const Info &L, const Info &R ) {
    return {
        L.sum + R.sum,
        max( L.mx, L.sum + R.mx )
    };
}

对于某个确定的等待时间 $b$，设这个叶子上所有邮件的编写时间总和为 $s$。当 $s>0$ 时，叶子摘要为 (s, s + b)；当 $s=0$ 时，这个值域位置应被忽略，所以 mx 取负无穷。

修改 $A_i$ 时，只要在当前 $B_i$ 对应叶子上增加差值。修改 $B_i$ 时，则从旧叶子减去 $A_i$，再向新叶子加上 $A_i$。

每次修改只影响一到两个叶子，单次复杂度为 $O(\log(N+Q))$。算上预处理与离散化，总复杂度为 $O((N+Q)\log(N+Q))$，空间复杂度为 $O(N+Q)$。

这道题对信息合并的增量不在前后缀接口，而在合并方向本身。merge(L,R) 描述先执行左区间再执行右区间，交换左右区间会改变摘要语义。

记录

• 来源：ABC467 A~F 中的 F 题记录。
• 归属：线段树信息合并、排序贪心与交换论证。
• 新增：交换论证推出按等待时间降序处理，之后再用有方向的区间摘要动态维护这一顺序。
• 生命周期：migrate。
• 后续：线段树信息合并 已吸收有方向摘要示例；排序贪心与交换论证尚未有完整接管节点，Execution Status 为 pending。