CF2257F2 Beaver's Jumping Track (Hard Version)

这是该问题的难度较高版本。与简单版本的区别在于本题中对 $x$ 的限制更高，时间限制也更严格。只有在解决了所有版本的问题后，才能进行 hack。 现在，Beaver 正在锻炼自己跳远的能力。Beaver 目前能跳 $x$ 米。然而，仅仅是尽力一跳到底既容易又无趣。因此，Beaver 设计了一条独特的跳远训练跑道。 这条跑道由 $n$ 个平台组成；每个平台由 $d_i$ 米的格子组成。如果 Beaver 站在第 $i$ 个平台，从上面起跳后又落回同一平台，那么会被记 $s_i$ 个罚分；否则不会有任何罚分。Beaver 可以向前跳任意小于等于 $x$ 格的整数距离。注意，Beaver 一次跳跃可以直接越过一个或多个平台，不必落在这些平台上。 Beaver 拥有无限的计算能力，并且总是能选择最优路线，使经过整条赛道时累积罚分最小。此外，赛道是动态变化的，有时某些平台的长度和罚分会更改。你需要学会计算：当 Beaver 站在第 $l$ 个平台的第一个格子出发，到达第 $r$ 个平台的最后一个格子时，最小的累计罚分是多少。

第一行包含三个整数 $n$、$q$、$x$，分别表示赛道的平台数、查询数、最大跳跃距离（$1 \leq n \leq 10^6$，$1 \leq q \leq 10^4$，$1 \leq x \leq 10$）。 第二行包含 $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 翻译