CF1922D Berserk Monsters

Monocarp 正在玩一款电脑游戏（又一次）。你猜他在做什么？没错，就是在杀怪物。 有 $n$ 个怪物排成一排，从 $1$ 到 $n$ 编号。第 $i$ 个怪物有两个参数：攻击值 $a_i$ 和防御值 $d_i$。为了杀死这些怪物，Monocarp 对它们施加了狂暴法术，让它们互相攻击，而不是攻击 Monocarp 的角色。 战斗共进行 $n$ 轮。每一轮，发生如下事件： - 首先，每个存活的怪物 $i$ 会对其左边最近的存活怪物（如果存在）和右边最近的存活怪物（如果存在）各造成 $a_i$ 点伤害； - 然后，每个在本轮受到的总伤害超过其防御值 $d_j$ 的存活怪物 $j$ 会死亡。也就是说，第 $j$ 个怪物当且仅当其防御值 $d_j$ 严格小于本轮受到的总伤害时会死亡。 请你计算每一轮中死亡的怪物数量。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含三行： - 第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）； - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）； - 第三行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$（$1 \le d_i \le 10^9$）。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数。第 $i$ 个整数表示第 $i$ 轮中死亡的怪物数量。

示例第一个测试用例的解释： 在第一轮中，发生如下事件： - 怪物 $1$ 对怪物 $2$ 造成 $3$ 点伤害； - 怪物 $2$ 对怪物 $1$ 和怪物 $3$ 各造成 $4$ 点伤害； - 怪物 $3$ 对怪物 $2$ 和怪物 $4$ 各造成 $7$ 点伤害； - 怪物 $4$ 对怪物 $3$ 和怪物 $5$ 各造成 $5$ 点伤害； - 怪物 $5$ 对怪物 $4$ 造成 $10$ 点伤害； - 怪物 $1$ 没有死亡，因为它受到 $4$ 点伤害，防御值为 $4$； - 怪物 $2$ 死亡，因为它受到 $10$ 点伤害，防御值为 $9$； - 怪物 $3$ 死亡，因为它受到 $9$ 点伤害，防御值为 $1$； - 怪物 $4$ 没有死亡，因为它受到 $17$ 点伤害，防御值为 $18$； - 怪物 $5$ 死亡，因为它受到 $5$ 点伤害，防御值为 $1$。 第一轮后，怪物 $1$ 和 $4$ 仍然存活。 在第二轮中，发生如下事件： - 怪物 $1$ 对怪物 $4$ 造成 $3$ 点伤害； - 怪物 $4$ 对怪物 $1$ 造成 $5$ 点伤害； - 怪物 $1$ 死亡，因为它受到 $5$ 点伤害，防御值为 $4$； - 怪物 $4$ 没有死亡，因为它受到 $3$ 点伤害，防御值为 $18$。 接下来的三轮，只有第 $4$ 个怪物存活，所以没有任何事情发生。 由 ChatGPT 4.1 翻译