给定序列 $a_1,\dots,a_n$ 和阈值 $m$。对于每个前缀 $k$，定义 $f(k)$ 为从中选出最多组不交叉配对（按顺序两两配对）且每对满足 $x \oplus y < m$ 的组数。要求输出一个长度为 $n$ 的字符串，第 $k$ 位为 Y 当且仅当 $f(k) > f(k-1)$。

• 性质

  对于这种的题目有一个比较板也比较常见的性质就是能配对就配对，感性理解一下也是比较显然的，因为如果有忽略的，那么在跳过后就没有机会再配对了。

我们可以就直接转化为判断上一个配对成功的位置到 $k$ 中间有无可以直接配对的，然后对于异或我们会很自然想到 01trie ，然后考虑每次配对完清空字典树。

根据数据范围，不难发现这个方法太爆了，而且很明显有些内容就比较的多余，例如可以直接比较前几位。所以考虑换掉字典树，改成用数组维护：

由于会立即配对，所以每个位置就只会出现不大于两次。

我们考虑可以类似于字典树暴力维护所有的答案，详细来说就是下面:

令 $t = \lfloor \log_2 m \rfloor$，即 $2^t \le m < 2^{t+1}$。
对于任意两个数 $x, y$，若 $x \oplus y < m$，则它们的二进制表示在高于 $t$ 的位上必须相同，且在第 $t$ 位上要么相同，要么不同但低位异或后整体仍小于 $m$。

考虑下面的过程:

• 从左到右扫描每个数 $a_i$。

• 令 $h = a_i \gg t$。检查 $S$ 中是否存在某个数 $y$ 使得 $y \gg t = h$ 或 $y \gg t = h \oplus 1$，且 $y \oplus a_i < m$。

• 若存在，则配对成功，答案增加 1，并将 $S$ 中 所有当前未配对的数清空。

• 若不存在，则将 $a_i$ 加入 $S$。

下面就是要维护这个快速配对，考虑对于每一个前缀开一个数字，然后进行暴力的判断:

• 使用数组记录当前的 $h$ 所代表的数。
• 同时维护一个“最近一次配对位置” l，以及一个栈或列表记录自 l 以来加入的所有数的值，以便在配对时快速清零。
• 如果成功配对，更新 l。

或许这里也可以使用哈希 map？

时间复杂度为 $O(n)$,空间为 $O(V)$。