CF2257F2.Beaver's Jumping Track (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, the constraint on $x$ and time limit are higher. You can hack only if you solved all versions of this problem.

The Beaver is training to jump long distances. The Beaver can already jump $x$ meters. However, just jumping as far as possible is easy and boring. Therefore, the Beaver has created an unusual training track for jumping.

The track consists of $n$ platforms; each platform consists of $d_i$ meter cells. If the Beaver stands on platform number $i$, jumps, and lands back on the same platform, this results in $s_i$ penalty points being awarded; otherwise, no penalty points are given. The Beaver can jump forward any integer number of cells less than or equal to $x$. Note that the Beaver can skip one or more platforms in a single jump without landing on them at all.

The Beaver has unlimited computational power in its mind and always jumps in such a way as to minimize the total penalty for passing the track. Moreover, the track is not constant, and sometimes the lengths and penalties of some platforms change. Learn to calculate what penalty the Beaver will get if it starts standing on the first cell of platform number $l$ and finishes standing on the last cell of platform number $r$.

这是该问题的困难版本。两个版本的区别在于，本版本中对 $x$ 的约束以及时间限制更高。仅当您解决了该问题的所有版本后，才可进行 hack。

海狸正在训练长距离跳跃。海狸当前已能跳跃 $x$ 米。然而，单纯尽可能跳得更远既简单又乏味。因此，海狸设计了一条独特的跳跃训练赛道。

该赛道由 $n$ 个平台组成；每个平台由 $d_i$ 米长的格子构成。若海狸站在编号为 $i$ 的平台上起跳，并最终落回同一平台，则将被罚 $s_i$ 分；否则不扣分。海狸每次跳跃可向前跨越任意不超过 $x$ 的正整数个格子。注意：海狸单次跳跃可跳过一个或多个平台，且完全不落在这些被跳过的平台上。

海狸拥有无限的脑内计算能力，总能以使通过整条赛道所受总罚分最小的方式跳跃。此外，赛道并非一成不变，有时某些平台的长度和罚分会动态更新。请实现一种算法，用以计算：当海狸从编号为 $l$ 的平台的第一个格子出发，并最终落在编号为 $r$ 的平台的最后一个格子时，所受的总罚分是多少。

The first line contains three integers $n$, $q$, $x$ — the number of sections of the track, the number of queries, and the maximum jump length, respectively ($1 \leq n \leq 10^6$; $1 \leq q \leq 10^4$; $1 \leq x \leq 10$).

The second line contains $n$ integers $d_i$ — the lengths of the platforms ($1 \leq d_i \leq 10^7$).

The third line contains $n$ integers $s_i$ — the penalties ($1 \leq s_i \leq 10^5$).

The following $q$ lines describe the queries in one of the following formats:

1. "1 $i$ $v$" — set the length of the $i$-th platform to $v$ ($1 \leq i \leq n$; $1 \leq v \leq 10^7$);
2. "2 $i$ $y$" — set the penalty on the $i$-th platform to $y$ ($1 \leq i \leq n$; $1 \leq y \leq 10^5$);
3. "? $l$ $r$" — calculate the minimum penalty for passing the track consisting of platforms from $l$ to $r$ ($1 \leq l \leq r \leq n$).

第一行包含三个整数 $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$ 行描述了 $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$）。

For each query of the third type, output a single number on a separate line — the minimum penalty.

对于每个第三种类型的查询，在单独一行输出一个数字——最小罚值。

During the first query, the lengths of the course sections are $[4, 2, 5]$ with costs $[4, 2, 7]$; the optimal route is

1 \\rightarrow 4 \\rightarrow 6 \\rightarrow 8 \\rightarrow 11$$ In this case, the penalty is $4 + 0 + 0 + 7 = 11$. Before the second query, the penalty of the second course increased, but we never get it; thus, the answer to this query is also $11$. Before the third query, we have the lengths of the courses $[2, 2, 5]$; then the route $$1 \\rightarrow 4 \\rightarrow 6 \\rightarrow 9$$ gives a penalty of 7, as the only penalizing jump is within one platform: $6 \rightarrow 9$. 第一次查询时，课程段的长度为 $[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$。