CF2042F.Two Subarrays

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。

我们定义子数组 $[l, r]$ 的代价为 $a_l + a_{l + 1} + \cdots + a_r + b_l + b_r$。如果 $l = r$，那么代价计算为 $a_l + 2 \cdot b_l$。

你需要执行以下三种类型的查询：

• "1 $p$ $x$" — 把 $a_p$ 更新为 $x$；
• "2 $p$ $x$" — 把 $b_p$ 更新为 $x$；
• "3 $l$ $r$" — 在区间 $[l, r]$ 内找到两个不相交且非空的子数组，使它们的总代价最大，并输出这个总代价。

第一行是一个整数 $n$，表示数组的长度（$2 \le n \le 2 \cdot 10^5$）。

第二行是 $n$ 个整数，分别表示数组 $a$ 的元素：$a_1, a_2, \dots, a_n$（每个 $a_i$ 满足 $-10^9 \le a_i \le 10^9$）。

第三行是 $n$ 个整数，分别表示数组 $b$ 的元素：$b_1, b_2, \dots, b_n$（每个 $b_i$ 满足 $-10^9 \le b_i \le 10^9$）。

第四行是一个整数 $q$，表示查询的数量（$1 \le q \le 2 \cdot 10^5$）。

接下来的 $q$ 行，每行一个查询，可能是以下三种之一：

• "1 $p$ $x$"：更新 $a$ 数组的第 $p$ 个元素为 $x$；
• "2 $p$ $x$"：更新 $b$ 数组的第 $p$ 个元素为 $x$；
• "3 $l$ $r$"：在区间 $[l, r]$ 找到两个不重叠且非空的子数组，使它们的总代价最大，并输出该代价。

可以保证至少存在一个第三种类型的查询。

对于每一个第三种类型的查询，输出在区间 $[l, r]$ 内的两个不相交且非空子数组的最大可能总代价。

本翻译由 AI 自动生成