糖果括号¶

预估时间限制：1 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

糖果工坊把糖果和括号形糖衣串在一起，推出了可以从两端不断加料的试吃串。除了香甜的普通糖果，里面还混着芥末味、苦瓜味等怪味糖果：有的增加甜蜜值，有的反而扣分，括号形糖衣也有自己的甜蜜值。

顾客只能选取连续的一段，而且其中的括号必须完整匹配。工坊想在每次加料后找出甜蜜值最高的可选片段；如果实在没有合口味的，也可以一颗不选。

一个元素的类型为 \(0\)（左括号）、\(1\)（右括号）或 \(2\)（糖果），并带有整数甜蜜值，可以为负、零或正。串的甜蜜值是所有元素甜蜜值之和，括号的值也计入。

可匹配串恰好由以下规则生成：空串可匹配；单个糖果可匹配；在一个可匹配串外添加一对左右括号，所得串可匹配；两个可匹配串的连接可匹配。类型之外，甜蜜值不影响是否可匹配。

给定长度为 \(N\) 的初始串，依次进行 \(M\) 次操作。每次在当前串的左端或右端添加一个元素，修改持续生效。对子串取连续的一段，保持原顺序，不能跳过中间的负值元素；也允许取空串或整个串。求初始串和每次操作后，所有可匹配子串中的最大甜蜜值。空串的甜蜜值为 \(0\) ，所以答案不会为负。

第一行两个整数 \(N,M\) .

第二行 \(N\) 个整数，依次表示初始元素的类型；第三行 \(N\) 个整数，依次表示它们的甜蜜值。若 \(N=0\) ，这两行都是空行。

接下来 \(M\) 行，每行三个整数 \(position,type,value\) .其中 \(position=0\) 表示添加到左端，\(position=1\) 表示添加到右端；\(type\) 是元素类型，\(value\) 是其甜蜜值，可能带负号。

输出 \(M+1\) 行。第一行是初始串的答案，其余各行依次是对应操作后的答案。

100
110
110

0 4


1 1 4000000000
0 0 4000000000
0 2 0
1 2 3

3 0
0 2 1
-3 -2 -4

第一组最初可以只选甜蜜值为 \(100\) 的糖果。左端加入 \(20\) 后，整个串的甜蜜值为 \(20-10+100=110\) ；最后加入的 \(-200\) 不必选择，答案仍为 \(110\) .

第二组的糖果甜蜜值为 \(10\) .两侧补齐括号后，整个可匹配串的甜蜜值为 \(-8+10-9=-7\) ，但仍可只选里面的糖果，答案为 \(10\) .左侧再加入 \(7\) 后，不能跳过中间的左括号直接选两颗糖果。最后右侧加入 \(20\) ，只选它或选择整个串都得到 \(20\) .

第三组从空串开始。孤立的右括号无法匹配；补上左括号后，两个括号的值都计入，得到 \(8000000000\) .

第四组所有元素的值都为负，选择空串得到 \(0\) .

本题由 Codex（GPT-6）加强：所有元素（包括括号）的甜蜜值范围扩展为 \(-4\times10^9\le value\le4\times10^9\) ，数据包含正负值混合的双端插入。

对所有数据，\(0\le N,M\le10^6\) ，\(position\in\{0,1\}\) ，\(type\in\{0,1,2\}\) .初始元素的类型和值满足同样的范围。允许零甜蜜值、空初始串和零次操作；结果需要使用有符号 64 位整数保存。