← 返回题目列表

Codeforces · 1958/J

J. 死灵法师

中文机器翻译题面 查看原题

Monocarp 正在玩电脑游戏。在这款游戏中,他的角色是一名死灵法师。他正在与编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 怪物战斗。每个怪物都有两个参数:生命值和力量。

Monocarp 考虑了 $$$q$$$ 的战斗场景。在每个场景中,他选择一些怪物$$$[l,r]$$$,并计算击败所有这些怪物所需的移动次数。

每个场景的进行如下。首先,Monocarp 杀死怪物 $$$l$$$ 并将其复活为僵尸(这不算是一次移动)。然后每次移动都会发生以下情况:令 $$$i$$$ 为 $$$[l, r]$$$ 段中第一个仍然活着的怪物的索引。所有僵尸都会攻击怪物 $$$i$$$,根据其总力量减少其生命值。之后,如果怪物 $$$i$$$ 的生命值为 $$$0$$$ 或更低,它就会死亡,Monocarp 会将其复活为僵尸。

怪物复活时,僵尸的力量等于怪物的力量。

帮助 Monocarp 计算每个场景需要多少步才能杀死该段中的所有怪物。

输入

第一行包含两个整数 $$$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^4$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个怪物的生命值。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^4$$$),其中 $$$b_i$$$ 是第 $$$i$$$ 个怪物的强度。

然后是 $$$q$$$ 行。其中第 $$$j$$$ 包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — 第 $$$j$$$ 场景的边界。

输出

对于每个场景,打印一个整数 - 杀死该段中所有怪物所需的移动次数。

示例

输入 #1

7 5
4 5 9 9 4 2 4
1 3 3 1 2 3 3
3 5
1 4
6 6
1 7
2 6

输出 #1

4
10
0
13
7