AT_asaporo2_c Paired Parentheses

给定两个长度为 $2N$ 的数列 $a$ 和 $b$，第 $i$ 个元素分别为 $a_i,b_i$。すぬけくん负责用这两个数列来计算长度为 $2N$ 的 **平衡括号序列** 的二元组 $(s, t)$ 的 *美丽值*。美丽值的计算方法如下： - 设 $X=0$。 - 对于每个 $i$，$1 \leq i \leq 2N$，如果 $s_i = t_i$，则将 $a_i$ 加到 $X$ 上，否则将 $b_i$ 加到 $X$ 上。 - 最终 $X$ 的值就是 $(s,t)$ 的美丽值。 现在给定 $Q$ 个查询，请依次处理。第 $i$ 个查询需将 $a_{p_i}$ 改为 $x_i$，$b_{p_i}$ 改为 $y_i$，然后求用当前 $a, b$ 能得到的所有平衡括号序列二元组的美丽值的最大值。 在本题中，平衡括号序列的定义如下之一： - 空字符串 - 对于某个平衡括号序列 $s$，将 `(`、$s$、`)` 按顺序连接得到的新字符串 - 对于平衡括号序列 $s,t$，将 $s$ 和 $t$ 按顺序连接得到的新字符串。

输入通过标准输入按以下格式给出。 > $N$ $Q$ > $a_1$ $a_2$ $\dots$ $a_{2N}$ > $b_1$ $b_2$ $\dots$ $b_{2N}$ > $p_1$ $x_1$ $y_1$ > $\vdots$ > $p_Q$ $x_Q$ $y_Q$

对于每个查询，输出一行，对于第 $i$ 个查询，输出该查询的答案。

### 数据范围 - $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$ ### 样例说明 1 - 第 1 个查询后，$a=(1,4,7,3),b=(4,6,3,3)$。当 $(s,t)=($`()()`$,``()()`$)$ 时，美丽值为 $15$，且最大。 - 第 2 个查询后，$a=(1,4,2,3),b=(4,6,5,3)$。当 $(s,t)=($`()()`$,`(())`$)$ 时，美丽值为 $15$，且最大。 由 ChatGPT 5 翻译