CF1659D.Reverse Sort Sum

Suppose you had an array $A$ of $n$ elements, each of which is $0$ or $1$.

Let us define a function $f(k,A)$ which returns another array $B$, the result of sorting the first $k$ elements of $A$ in non-decreasing order. For example, $f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$. Note that the first $4$ elements were sorted.

Now consider the arrays $B_1, B_2,\ldots, B_n$ generated by $f(1,A), f(2,A),\ldots,f(n,A)$. Let $C$ be the array obtained by taking the element-wise sum of $B_1, B_2,\ldots, B_n$.

For example, let $A=[0,1,0,1]$. Then we have $B_1=[0,1,0,1]$, $B_2=[0,1,0,1]$, $B_3=[0,0,1,1]$, $B_4=[0,0,1,1]$. Then $C=B_1+B_2+B_3+B_4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]$.

You are given $C$. Determine a binary array $A$ that would give $C$ when processed as above. It is guaranteed that an array $A$ exists for given $C$ in the input.

假设你有一个长度为 $n$ 的数组 $A$，其中每个元素均为 $0$ 或 $1$。

我们定义一个函数 $f(k,A)$，它返回另一个数组 $B$，该数组是将 $A$ 的前 $k$ 个元素按非递减顺序排序后得到的结果。例如，$f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$。注意，仅前 $4$ 个元素被排序。

现在考虑由 $f(1,A), f(2,A),\ldots,f(n,A)$ 生成的数组 $B_1, B_2,\ldots, B_n$。令 $C$ 为 $B_1, B_2,\ldots, B_n$ 的逐元素和（即对每个位置 $i$，$C[i] = B_1[i] + B_2[i] + \cdots + B_n[i]$）。

例如，设 $A=[0,1,0,1]$。则有：
$B_1=[0,1,0,1]$，
$B_2=[0,1,0,1]$，
$B_3=[0,0,1,1]$，
$B_4=[0,0,1,1]$。
于是 $C=B_1+B_2+B_3+B_4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]$。

现给你数组 $C$，请确定一个二进制数组 $A$，使得按上述过程处理 $A$ 后恰好得到 $C$。题目保证：对输入中给定的 $C$，总存在满足条件的数组 $A$。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

Each test case has two lines. The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($0 \leq c_i \leq n$). It is guaranteed that a valid array $A$ exists for the given $C$.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例包含两行。第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$0 \leq c_i \leq n$）。保证对于给定的 $C$，存在一个合法的数组 $A$。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a single line containing $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $0$ or $1$). If there are multiple answers, you may output any of them.

对于每个测试用例，输出一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（其中每个 $a_i$ 为 $0$ 或 $1$）。如果存在多个答案，你可以输出其中任意一个。

Here's the explanation for the first test case. Given that $A=[1,1,0,1]$, we can construct each $B_i$:

• $B_1=[\color{blue}{1},1,0,1]$;
• $B_2=[\color{blue}{1},\color{blue}{1},0,1]$;
• $B_3=[\color{blue}{0},\color{blue}{1},\color{blue}{1},1]$;
• $B_4=[\color{blue}{0},\color{blue}{1},\color{blue}{1},\color{blue}{1}]$

And then, we can sum up each column above to get $C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]$.

以下是第一个测试用例的解释。给定 $A=[1,1,0,1]$，我们可以构造每个 $B_i$：

• $B_1=[\color{blue}{1},1,0,1]$；
• $B_2=[\color{blue}{1},\color{blue}{1},0,1]$；
• $B_3=[\color{blue}{0},\color{blue}{1},\color{blue}{1},1]$；
• $B_4=[\color{blue}{0},\color{blue}{1},\color{blue}{1},\color{blue}{1}]$

然后，我们将上述每列分别求和，得到 $C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]$。