邮件调度优化(Email Scheduling Optimization)

题目描述

给定长度为 N 的正整数列 A=(A₁,A₂,…,A_N)、B=(B₁,B₂,…,B_N)。

给定 Q 个查询，每个查询为以下两种之一：

• 1 i x：将 A_i 改为 x。
• 2 i x：将 B_i 改为 x。

每处理完一个查询后，求解以下问题并输出答案：

高橋君需要向 N 家公司各发送一封邮件，并收到每家的回复。

写发给第 j 家公司的邮件需要 A_j 分钟，发送后过 B_j 分钟收到回复。

他从时刻 0 开始写邮件，可以按任意顺序写这 N 封邮件，但不能同时写两封以上。

求他收齐所有回复的最早可能时刻。发送邮件本身耗时忽略不计。

输入格式

N Q
A1 A2 … AN
B1 B2 … BN
query1
query2
⋮
queryQ

每个查询为 1 i x 或 2 i x。

输出格式

输出共 Q 行，第 q 行输出处理完第 q 个查询后问题的答案。

样例输入 #1

3 3
4 6 7
4 6 7
1 2 1
2 3 7
2 3 1

样例输出 #1

16
16
13

数据范围

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 1 ≤ A_j, B_j ≤ 10⁹
• 每个查询中 1 ≤ i ≤ N，1 ≤ x ≤ 10⁹
• 输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布