CF2262B Culling Game

Bessie 正在制作一档名为 Moojutsu Cowsen 的节目。在某一期节目中，她邀请了 $n$ 位术士，并将他们从左到右依次排成一行。第 $i$ 位术士的初始技能值为 $a_i$。 术士们进行一种 king-of-the-hill（擂台赛）式的比赛。最左侧的剩余术士最先作为“冠军”，他的当前技能值等于他的初始技能值。 然后，现任冠军将依次与其右侧剩余的每一位术士对决。假设当前冠军的技能值为 $s$，右侧下一个术士的技能值为 $x$。 如果 $s < x$，冠军会认输，对方成为新冠军，技能值变为 $x$。 否则，冠军战胜对手（包括 $s = x$ 的情况），并且冠军的技能值变为 $s + x$。 Bessie 认为认输的过程很无聊，所以在比赛开始前，她可以从队伍中移除一些术士。 你会得到一个长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$，其中 $p_i$ 是 $1 \sim n$ 的一个排列。对于每一个 $0 \le i \le n-1$，Bessie 会移除术士 $p_1,p_2,\ldots,p_i$，只保留剩下的术士参与比赛。如果 $i=0$，则没有人被移除。剩下术士的相对顺序保持不变。 请你对于每一个 $i$，求出只用剩下的术士进行比赛，最终出现了多少次“认输”。

每组数据包含若干个测试用例。第一行包含一个整数 $t$，表示测试用例数 $(1 \le t \le 10^4)$。 每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 2 \times 10^5)$。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1 \le a_i \le 10^9)$。 第三行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示 $1 \sim n$ 的一个排列。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出 $n$ 个整数。 第 $i$ 个数表示移除 $p_1,p_2,\ldots,p_{i-1}$ 后进行比赛，“认输”过程发生的次数。

对于第一个测试用例，答案为 $2,1,0,0$。 最开始的数组是 $[1,2,4,3]$。冠军（$1$）遇到 $2$ 时认输，$2$ 成为新冠军；然后 $2$ 遇到 $4$ 又认输，$4$ 成为新冠军；最后 $4$ 战胜 $3$，总共发生 $2$ 次认输。 去除术士 $1$ 后，剩余数组是 $[2,4,3]$。冠军 $2$ 遇到 $4$ 认输，$4$ 战胜 $3$，总共 $1$ 次认输。 去除 $1,2$ 后，剩余数组是 $[4,3]$。$4$ 直接战胜 $3$，$0$ 次认输。全部移除 $1,2,3$ 后，只剩 $[3]$，同样是 $0$ 次认输。 对于第二组数据，答案是 $1,0,2,1,0$。 最初的数组是 $[3,1,7,2,6]$：$3$ 战胜 $1$，技能变 $4$，遇到 $7$ 认输，$7$ 成为新冠军；$7$ 战胜 $2$，变 $9$，再战胜 $6$，共 $1$ 次认输。 移除术士 $3$（技能 $7$）后，数组是 $[3,1,2,6]$，冠军 $3$ 一路战胜其他人，无一次认输。 再移除术士 $1$ 后剩 $[1,2,6]$，$1$ 对 $2$ 认输，$2$ 对 $6$ 认输，共 $2$ 次认输。 再移除 $5$ 后剩 $[1,2]$，$1$ 认输给 $2$，$1$ 次认输。再移除 $2$，只剩 $[2]$，$0$ 次认输。 由 ChatGPT 5 翻译