驾照考试 - Problem

Misha 是一名新手司机。在顺利通过驾照考试的理论部分后，他只剩下最后一步——通过实际驾驶考试。然而，事情并没有那么简单，因为 Misha 不知道如何在冰面上开车。

考试场地位于一片空地上，由 $n$ 个交叉路口组成，对于 $1$ 到 $n-1$ 之间的每个 $i$，第 $i$ 个和第 $(i+1)$ 个交叉路口之间有一条长度为 $d_i$ 的道路。初始时，第 $i$ 个交叉路口有 $w_i$ 单位的冰。

考试时，考官会选择赛道的一个连续子段 $[l, r]$：包含编号从 $l$ 到 $r$ 的所有交叉路口以及它们之间的所有道路。考试赛道必须是环形的，因此在选择 $l$ 和 $r$ 后，考官还会用一条长度为 $x$ 的临时道路将编号为 $l$ 和 $r$ 的交叉路口连接起来。

考官不想让 Misha 通过考试，因此考试赛道上的所有道路都必须覆盖上冰。为此，必须将冰从道路连接的交叉路口移出；一单位的冰可以覆盖一单位的道路。因此，移到道路上的冰的总量必须不小于其长度。当然，从每个交叉路口移到两条相邻道路上的冰的总量不能超过该路口现有的冰量。

不幸的是，目前的冰量可能不足以覆盖所有道路，因此考官想知道，为了使所有道路都能被覆盖并阻止 Misha 通过考试，需要向交叉路口添加的冰的总量最少是多少。

你需要处理三种类型的查询：改变某个交叉路口的冰量，改变某条道路的长度，以及解决赛道子段的问题。

第一行包含两个整数 $n$ 和 $q$ —— 分别表示交叉路口的数量和查询的数量（$2 \le n \le 2 \cdot 10^5$，$1 \le q \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $w_i$ —— 每个交叉路口的初始冰量（$1 \le w_i \le 10^9$）。

第三行包含 $n-1$ 个整数 $d_i$ —— 相邻交叉路口之间每条道路的初始长度（$1 \le d_i \le 10^9$）。

接下来的 $q$ 行描述查询：

$1 \ p \ x$ ($1 \le p \le n, 1 \le x \le 10^9$) —— 执行赋值 $w_p := x$；
$2 \ p \ x$ ($1 \le p \le n-1, 1 \le x \le 10^9$) —— 执行赋值 $d_p := x$；
$3 \ l \ r \ x$ ($1 \le l < r \le n, 1 \le x \le 10^9$) —— 确定对于由编号从 $l$ 到 $r$ 的交叉路口组成的子段，在添加长度为 $x$ 的临时道路闭合环路后，为了覆盖所有道路，需要向交叉路口添加的冰的最小总量。注意，第三类查询不会改变交叉路口的冰量；你只需要回答为了覆盖所有道路需要添加多少冰。每次查询后，考官会拆除临时道路，因此在其他查询中不需要考虑它。

保证至少有一个第三类查询。

对于每个第三类查询，输出为了覆盖整个环形赛道而需要向交叉路口添加的冰的最小总量。

6 7
5 9 5 1 9 5
4 8 10 4 5
3 1 6 12
3 4 6 5
2 4 1
1 6 3
3 4 6 5
1 2 3
3 2 3 6

下图展示了样例的说明。虚线表示闭合环路的临时道路。交叉路口处标注的是当前冰量和添加的冰量，道路上标注的是从交叉路口移出的冰量。

QOJ.ac