P4957. 闪耀之塔

场次：2026年5月16日-开发岗 · 来源：CodeFun2000 P4957

题目描述

在一座珍宝工坊中，有一排从左到右放置的展示盒，初始为空。工匠需要依次将 $n$ 个宝石放入盒子中。每个宝石都有一个闪耀值，按照放入顺序编号为 $1$ 到 $n$。放置规则如下：

• 从最左侧的盒子开始向右检查；
• 若当前盒子为空，或盒内最上层宝石的闪耀值严格大于当前宝石的闪耀值，则将当前宝石叠放到该盒子顶部；
• 否则继续检查下一个盒子；
• 若检查完所有非空盒子后仍未放入，则在最右侧新建一个展示盒，并将当前宝石放入其中。

每次放入一个宝石后，记录每个盒子中宝石的数量（称为层数）。请你求出每次放入后所有盒子层数的异或和，并依次输出。

数据范围：输入包含多组测试数据，组数 $T$ 满足 $1 \le T \le 2 \times 10^5$。所有测试数据中宝石的总数（即 $\sum n$）不超过 $4 \times 10^5$。单个测试用例中的宝石数量 $n$ 满足 $1 \le n \le 4 \times 10^5$。每个宝石的闪耀值为正整数，且不超过 $10^9$。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。接下来对于每组数据：第一行包含一个整数 $n$，表示该组宝石的数量；第二行包含 $n$ 个整数，依次表示每个宝石的闪耀值，整数之间以空格分隔。

输出格式

对于每组数据，输出一行 $n$ 个整数，用空格分隔，第 $i$ 个整数表示放入前 $i$ 个宝石后所有盒子层数的异或和。

示例

示例 1

输入：

1
5
5 4 3 2 1

输出：

1 2 3 4 5

说明：

初始无任何展示盒。放入第 1 个宝石（闪耀值 5），创建盒子 1，高度为 1，当前所有盒子层数的异或和为 $1$。

放入第 2 个宝石（闪耀值 4），第一个盒子顶部为 5，严格大于 4，因此放入该盒，高度由 1 变为 2，异或和变为 $1 \oplus 1 \oplus 2 = 2$。

同理，后续宝石 3、2、1 均放入唯一的盒子中，使其高度依次变为 3、4、5，每次异或和即为当前高度。最终输出序列为 1 2 3 4 5。

示例 2

输入：

1
6
3 5 2 4 2 1

输出：

1 0 3 0 1 0

说明：

初始无盒子。

• 放入 3：新建盒子，高度 1，异或和 $1$。
• 放入 5：无盒子顶部严格大于 5，新建第二个盒子，高度 1，异或和 $1 \oplus 1 = 0$。
• 放入 2：第一个盒子顶部 3 严格大于 2，放入后高度由 1 变为 2，异或和 $0 \oplus 1 \oplus 2 = 3$。
• 放入 4：当前顶部为 $[2,5]$，第二个盒子顶部 5 严格大于 4，放入后高度由 1 变为 2，异或和 $3 \oplus 1 \oplus 2 = 0$。
• 放入 2：顶部变为 $[2,4]$，第一个严格大于 2 的是第二个盒子（顶部 4），放入后高度由 2 变为 3，异或和 $0 \oplus 2 \oplus 3 = 1$。
• 放入 1：第一个盒子顶部 2 严格大于 1，高度由 2 变为 3，异或和 $1 \oplus 2 \oplus 3 = 0$。

依次输出每次操作后的异或和：1 0 3 0 1 0。

示例 3

输入：

1
4
10 10 10 10

输出：

1 0 1 0

说明：

所有宝石的闪耀值均为 10。

放入第 1 个宝石：新建盒子 1，高度为 1，异或和 $1$。

放入第 2 个宝石：当前唯一盒子的顶部为 10，并不严格大于 10，因此无法放入，只能新建盒子 2，高度为 1，此时两个高度 1 的盒子异或和变为 $1 \oplus 1 = 0$。

放入第 3 个宝石：依然无法放入已有盒子，新建盒子 3，高度 1，异或和变为 $0 \oplus 1 = 1$。

放入第 4 个宝石：继续新建盒子 4，异或和回到 $0$。

由此可见，当所有闪耀值相等时，每次均会新建盒子，异或和序列在 1 与 0 之间交替。最终输出 1 0 1 0。