解题思路

对于每个位置 $i$，需要判断右侧是否存在某个 $a_j$，满足 $j>i$ 且：

$a_i \text{ xor } a_j \ge \text{maxA}$

这是一个典型的“在一组数中寻找与当前数异或最大值”的问题，可以使用二进制字典树。

核心做法：

题目内容

给定一个长度为 $n$ 的整数数组 $\{a_1,a_2,\dots,a_n\}$。记数组中的最大值为 $\max\{a_1,a_2,\dots,a_n\}$，简称为 $\text{maxA}$。

对于每一个位置 $i$，我们想知道：是否存在下标严格大于 $i$ 的某个元素 $a_j$（即 $j > i$），使得将 $a_i$ 与它进行按位异或（即 $a_i \text{ xor } a_j$）后，结果大于等于 $\text{maxA}$。如果存在，记该位置为可行；否则为不可行。

输入描述

第一行输入一个整数 $n\ (1 \le n \le 2 \times 10^5)$，表示数组长度。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1 \le a_i \le 10^9)$，表示数组元素。

输出描述

输出一个仅包含数字字符 $'0'$ 与 $'1'$ 的字符串，长度为 $n$。第 $i$ 个字符表示位置 $i$ 是否可行：可行输出 $'1'$，不可行输出 $'0'$。

样例1

输入

5
1 2 3 4 5

输出

11100

说明

数组最大值为 $\text{maxA} = 5$。

• 位置 $1$：可与右侧的 $4$ 异或，$1 \text{ xor } 4 = 5 \ge 5$，可行；
• 位置 $2$：可与右侧的 $4$ 异或，$2 \text{ xor } 4 = 6 \ge 5$，可行；
• 位置 $3$：可与右侧的 $4$ 异或，$3 \text{ xor } 4 = 7 \ge 5$，可行；
• 位置 $4$：右侧仅有 $5$，$4 \text{ xor } 5 = 1 < 5$，不可行；
• 位置 $5$：右侧无元素，不可行。