CF1030F Putting Boxes Together

有一条无限长的直线，由若干格子组成。在这条直线的某些格子上放有 $n$ 个箱子。第 $i$ 个箱子位于格子 $a_i$ 上，重量为 $w_i$。所有 $a_i$ 互不相同，并且对于所有合法的 $i$，都有 $a_{i-1} < a_i$。 你希望将一些箱子聚集在一起。将编号在区间 $[l, r]$ 的箱子聚集在一起，意味着你需要移动它们，使得它们的位置变为某个连续区间 $[x, x + (r - l)]$。 每一步你可以将任意一个箱子移动到相邻的格子上，只要该格子没有其他箱子（即你可以选择 $i$ 并将 $a_i$ 加 $1$ 或减 $1$，所有位置始终保持互不相同）。将第 $i$ 个箱子移动一格需要消耗 $w_i$ 单位能量。你可以以任意顺序、任意次数移动任意箱子。 有时某些箱子的重量会发生变化，因此有两种类型的操作： 1. $id$ $nw$ ——将编号为 $id$ 的箱子的重量 $w_{id}$ 变为 $nw$。 2. $l$ $r$ ——你需要计算将编号在 $[l, r]$ 区间内的箱子聚集在一起所需的最小总能量。由于答案可能很大，请输出其对 $1000\,000\,007 = 10^9 + 7$ 取模的结果。注意，箱子在查询过程中不会实际移动，你只需计算答案。 注意，你需要最小化原始答案，而不是其对 $10^9 + 7$ 取模的结果。所以如果有两个可能的答案 $2 \cdot 10^9 + 13$ 和 $2 \cdot 10^9 + 14$，你应该选择第一个并输出 $10^9 + 6$，即使第二个答案取模后为 $0$。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$），分别表示箱子的数量和操作的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每个箱子的位置。所有 $a_i$ 互不相同，且 $a_{i-1} < a_i$。 第三行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^9$），表示每个箱子的初始重量。 接下来 $q$ 行，每行描述一个操作。 每个操作由两个整数 $x$ 和 $y$ 组成。如果 $x < 0$，则为第一种操作，其中 $id = -x$，$nw = y$（$1 \le id \le n$，$1 \le nw \le 10^9$）。如果 $x > 0$，则为第二种操作，其中 $l = x$，$r = y$（$1 \le l_j \le r_j \le n$）。$x$ 不会等于 $0$。

对于每个第二种类型的操作，输出一行答案。由于答案可能很大，请输出其对 $1000\,000\,007 = 10^9 + 7$ 取模的结果。

让我们逐步分析样例中的操作： 1. $1\ 1$ —— 只有一个箱子，无需移动，能量消耗为 $0$。 2. $1\ 5$ —— 可以将箱子移动到区间 $[4, 8]$：$1 \cdot |1 - 4| + 1 \cdot |2 - 5| + 1 \cdot |6 - 6| + 1 \cdot |7 - 7| + 2 \cdot |10 - 8| = 10$。 3. $1\ 3$ —— 可以将箱子移动到区间 $[1, 3]$。 4. $3\ 5$ —— 可以将箱子移动到区间 $[7, 9]$。 5. $-3\ 5$ —— 将 $w_3$ 从 $1$ 改为 $5$。 6. $-1\ 10$ —— 将 $w_1$ 从 $1$ 改为 $10$。此时权值为 $w = [10, 1, 5, 1, 2]$。 7. $1\ 4$ —— 可以将箱子移动到区间 $[1, 4]$。 8. $2\ 5$ —— 可以将箱子移动到区间 $[5, 8]$。 由 ChatGPT 4.1 翻译