CF2257F1 Beaver's Jumping Track (Easy Version)

这是该题的简单版本。本版本与其他版本的区别在于本题 $x$ 和时间限制较低。只有在你解决了所有版本后才能 hack 其他人。 小海狸正在训练跳远。小海狸现在已经能跳 $x$ 米了。然而，仅仅一直尽力跳远太简单且无聊。因此，小海狸为自己的跳跃训练设计了一条与众不同的赛道。 赛道由 $n$ 个平台组成，每个平台的长度为 $d_i$ 米。如果小海狸站在第 $i$ 个平台上跳跃，并最终落在同一个平台上，则会被记上 $s_i$ 分的罚分；否则，不记罚分。小海狸可以选择向前跳任意不超过 $x$ 的整数距离。注意，小海狸可以一次跳跃跨越一个或多个平台，并且不必落在这些平台中间。 小海狸的大脑拥有无限的计算能力，并且她总是以使通过赛道所获得的总罚分最小的方式跳跃。此外，赛道并不是固定不变的，有时某些平台的长度和罚分会发生变化。学习如何计算：如果小海狸从第 $l$ 个平台的首个格子出发，到第 $r$ 个平台的最后一个格子结束，将会获得多少罚分。

第一行包含三个整数 $n$、$q$、$x$，表示赛道的段数、询问数量和最大跳跃距离（$1 \leq n \leq 10^6$；$1 \leq q \leq 10^4$；$1 \leq x \leq 5$）。 第二行包含 $n$ 个整数 $d_i$，表示每个平台的长度（$1 \leq d_i \leq 10^7$）。 第三行包含 $n$ 个整数 $s_i$，表示每个平台的罚分（$1 \leq s_i \leq 10^5$）。 接下来的 $q$ 行，每行描述一种操作，格式如下： 1. "1 $i$ $v$" — 将第 $i$ 个平台的长度修改为 $v$（$1 \leq i \leq n$；$1 \leq v \leq 10^7$）； 2. "2 $i$ $y$" — 将第 $i$ 个平台的罚分修改为 $y$（$1 \leq i \leq n$；$1 \leq y \leq 10^5$）； 3. "? $l$ $r$" — 计算从第 $l$ 个平台的首个格子到第 $r$ 个平台的末尾格子，最小总罚分是多少（$1 \leq l \leq r \leq n$）。

对于每个第三种类型的询问，在单独的一行输出一个数字，表示最小总罚分。

在第一次询问时，赛道段长为 $[4, 2, 5]$，罚分为 $[4, 2, 7]$；最优路线为 $$ 1 \rightarrow 4 \rightarrow 6 \rightarrow 8 \rightarrow 11 $$ 此时的罚分为 $4 + 0 + 0 + 7 = 11$。 在第二次询问前，第二段赛道的罚分增加了，但我们不会得到它，所以答案也是 $11$。 第三次询问前，赛道长度为 $[2, 2, 5]$；则可选路线为 $$ 1 \rightarrow 4 \rightarrow 6 \rightarrow 9 $$ 总罚分为 7，因为唯一一次在平台内跳跃发生在 $6 \rightarrow 9$。 由 ChatGPT 5 翻译