分数: 700 点
问题陈述
给你两个序列 a 和 b,长度均为 2N。的 i- 第一个元素 分别是 a 和 b 是 a_i 和 b_i。 Snuke 使用这些序列来计算 美女 对 括号的平衡序列 (定义如下)长度 2N。 一对的美丽 (s,t) 计算如下:
- 让 X=0.
- 对于每个 i 之间 1 和 2N (含),增量 X by a_i if s_i = t_i,并递增 X by b_i 否则。
- 的美丽 (s,t) 是最终值 X.
你将得到 Q 查询。按顺序处理它们。 在 i-第次查询,更新值 a_{p_i} to x_i,以及值 b_{p_i} to y_i。然后,找到一对平衡的括号序列的最大可能的美感。
在这个问题中,只有下面的序列被定义为括号平衡序列。
- 空字符串
- 的串联
(, s,)按此顺序,其中 s 是括号的平衡序列 - 的串联 s, t 按此顺序,其中 s 和 t 是平衡的括号序列
约束
- 1 \leq N,Q \leq 10^{5}
- -10^{9} \leq a_i,b_i,x_i,y_i \leq 10^{9}
- 1 \leq p_i \leq 2N
- 所有输入值均为整数。
部分分数
- 在测试集中值得 200 点, N \leq 5 和 Q \leq 10.
- 在测试集中值得 300 点, Q = 1.
输入
输入由标准输入按以下格式给出:
N Q
a_1 a_2 ... a_{2N}
b_1 b_2 ... b_{2N}
p_1 x_1 y_1
:
p_Q x_Q y_Q
输出
打印 Q 行。的 i- 第行应包含对 i-第一个查询。
示例输入 1
2 2 1 1 7 3 4 2 3 3 2 4 6 3 2 5
示例输出 1
15 15
- 第一个查询更新 a 和 b to a=(1,4,7,3),b=(4,6,3,3)。最大可能的美丽是 15 为 (s,t) =(
()(),()()). - 第二个查询更新 a 和 b to a=(1,4,2,3),b=(4,6,5,3)。最大可能的美丽是 15 为 (s,t) =(
()(),(())).
示例输入 2
7 7 34 -20 -27 42 44 29 9 11 20 44 27 19 -31 -29 46 -50 -11 20 28 46 12 13 33 -22 -48 -27 35 -17 7 27 34 12 -2 22 4 -50 -12 3 -32 15 8 -7 23 3 -30 11 4 -2 23
示例输出 2
311 312 260 286 296 292 327