题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。

一个数组 $b$ 的美观度 $f(b)$ 定义为该数组中所有元素对 $(b_i, b_j)$（其中 $1 \le i \le j \le m$, $m$ 是 $b$ 的长度）的最大按位异或 (XOR) 值，即 $f(b) = \max_{1 \le i \le j \le m} (b_i \oplus b_j)$。

如果一个数组 $b$ 的美观度 $f(b) \ge k$，则称该数组是美丽的。

你需要从给定的数组 $a$ 中找出一个连续子数组 $a_{l \dots r}$ (即 $a_l, a_{l+1}, \dots, a_r$)，要求这个子数组是美丽的，并且其长度 $r - l + 1$ 尽可能小。

输出这个最小的长度。如果数组 $a$ 中不存在任何美丽的子数组，则输出 $-1$。

样例

输入 #1

6
5 0
1 2 3 4 5
5 7
1 2 3 4 5
5 8
1 2 3 4 5
5 7
3 5 1 4 2
5 3
3 5 1 4 2
6 71
26 56 12 45 60 27

输出 #1

1
2
-1
4
2
-1

样例解释:

• Case 1: k=0. 任何非空数组的 beauty 都是非负的，所以 beauty >= 0 恒成立。最短的子数组长度为 1。
• Case 2: k=7, a=[1,2,3,4,5]. 子数组 [3, 4] (长度 2) 的 beauty = max(3^3, 3^4, 4^4) = max(0, 7, 0) = 7. 因为 7 >= 7，所以 [3, 4] 是美丽的。长度为 1 的子数组 beauty 都是 0，不满足。所以最短长度是 2。
• Case 3: k=8, a=[1,2,3,4,5]. 最大的 XOR 值是 4^5=1, 3^5=6, 3^4=7, 2^5=7, 2^4=6, 2^3=1, 1^5=4, 1^4=5, 1^3=2, 1^2=3。最大是 7。没有子数组的 beauty >= 8。输出 -1。
• Case 4: k=7, a=[3,5,1,4,2]. 子数组 [3,5,1,4] (长度 4) 中，3^5=6, 3^1=2, 3^4=7, 5^1=4, 5^4=1, 1^4=5。最大 XOR 是 7。长度为 4。检查更短的：[3,5,1] max XOR=6; [5,1,4] max XOR=5; [1,4,2] max XOR=6; [3,5] XOR=6; [5,1] XOR=4; [1,4] XOR=5; [4,2] XOR=6。没有长度 < 4 的子数组 beauty >= 7。所以最短是 4。
• Case 5: k=3, a=[3,5,1,4,2]. 子数组 [3,5] 的 beauty = 3^5 = 6 >= 3。长度为 2。最短。
• Case 6: k=71, a=[…]. 经检查，没有任何子数组的最大 XOR 值 >= 71。输出 -1。

算法 (双指针 + 0-1 Trie)

$O(N \log A_{\max})$

思路分析

1. 问题目标: 寻找最短的子数组 $a[l \dots r]$ 使得 $\max_{l \le i \le j \le r} (a_i \oplus a_j) \ge k$。

2. 暴力法的局限: 直接枚举所有子数组 $a[l \dots r]$ (O(N²))，再计算每个子数组的美观度（对长度为 $m$ 的子数组，需要 O(m²) 次 XOR 运算，或使用 Trie 优化到 O(m log A_max)），总复杂度过高。

3. 双指针/滑动窗口的潜力: 题目要求最短的满足条件的子数组。这类问题通常可以用双指针（或滑动窗口）来优化。我们尝试固定右端点 $i$，然后找到尽可能大的左端点 $j$（即最小化窗口 $a[j \dots i]$ 的长度），使得 $f(a[j \dots i]) \ge k$。

4. 维护窗口和检查条件:

   • 我们使用两个指针 i（右端点）和 j（左端点），初始 j=0。
   • 我们从左到右移动右端点 i (从 0 到 n-1)。
   • 对于每个 i，我们将 $a_i$ 加入当前窗口 $a[j \dots i]$。
   • 我们需要高效地判断当前窗口 $a[j \dots i]$ 是否满足 $f(a[j \dots i]) \ge k$。
   • 同时，如果窗口满足条件，我们需要尝试将左端点 j 向右移动，以找到最短的满足条件的窗口。

5. 使用 0-1 Trie 优化:

   • 计算 $f(a[j \dots i]) = \max_{j \le x \le y \le i} (a_x \oplus a_y)$ 仍然比较困难。
   • 但是，我们可以利用 0-1 Trie（字典树）来高效地解决 “查询一个数与集合中某个数的最大异或值” 的问题。
   • 我们可以维护一个 0-1 Trie，存储当前窗口 $a[j \dots i]$ 中的所有数字。
   • 当右端点 i 移动时，我们将 $a_i$ 插入 Trie。
   • 当左端点 j 移动时，我们将 $a_j$ 从 Trie 中删除。
   • 关键检查点: 当我们将 $a_i$ 加入 Trie 后，我们可以查询与 $a_i$ 异或值最大的数是多少。令 query(x) 函数返回当前 Trie 中与 x 异或值最大的结果。如果 query(a_i) \ge k，这意味着新加入的元素 $a_i$ 与窗口中已有的某个元素 $a_p$ ($j \le p \le i$) 的异或值达到了 $k$ 或更高。这足以证明当前窗口 $a[j \dots i]$ 的美观度 $f(a[j \dots i]) \ge k$。
   • 为什么这个检查足够？ 虽然 $f(a[j \dots i])$ 的最大值可能不由 $a_i$ 贡献，但我们寻找的是 最短 的美丽子数组。如果一个子数组 $a[l \dots r]$ 是最短的美丽子数组，那么当我们的右指针 i 移动到 r 时，并且左指针 j 恰好为 l 时，一定存在某个机制让我们识别出 $a[l \dots r]$ 是美丽的，并记录下它的长度。如果 $f(a[l \dots r])$ 的最大值是由 $a_p \oplus a_q$ ($l \le p \le q \le r$) 得到的，那么当右指针 i 到达 $\max(p, q)$ 时，我们的检查（如果设计得当）就应该能捕捉到这个条件。
   • 我们采用的策略是：对于当前的右端点 i，检查新加入的 $a_i$ 是否能与窗口 $a[j \dots i]$ 中的某个数 $a_p$ 形成 $\ge k$ 的异或值。如果是，则 $a[j \dots i]$ 就是一个美丽的子数组。此时，我们记录下它的长度 i - j + 1，并尝试缩小窗口（增加 j）看是否还能保持美丽。

6. 双指针配合 Trie 的流程:

   • 初始化 ans = n + 1 (一个比最大可能长度大的值)，j = 0。
   • 初始化一个空的 0-1 Trie (init())。
   • 遍历 i 从 0 到 n-1：
     1. 将 $a_i$ 插入 Trie (add(a[i], 1))。
     2. 核心循环: while (j <= i && query(a[i]) >= k):
        • 这个 while 条件检查：当前元素 $a_i$ 与窗口 $a[j \dots i]$ 中的某个元素（记为 $a_p$）的最大异或值是否 $\ge k$。
        • 如果条件成立，说明子数组 $a[j \dots i]$ 是美丽的（因为 $a_i \oplus a_p \ge k$）。
        • 更新答案：ans = min(ans, i - j + 1)。
        • 尝试缩小窗口：将窗口最左端的元素 $a_j$ 从 Trie 中删除 (add(a[j], -1)）。
        • 将左指针右移：j++。
        • 这个 while 循环会一直执行，直到 $a_i$ 与当前（缩小的）窗口 $a[j \dots i]$ 中的所有元素的最大异或值小于 $k$ 为止。此时的 j 是对于固定的 i，使得 $a[j \dots i]$ 满足 query(a[i]) >= k 的最小起始位置（即找到了最短的以 $a_i$ 为 “触发条件” 的美丽子数组）。
   • 遍历结束后，如果 ans > n，说明没有找到任何美丽的子数组，将 ans 设为 -1。
   • 输出 ans。

7. 0-1 Trie 实现细节:

   • 由于需要删除操作，Trie 的每个节点需要存储一个计数 cnt，表示有多少个数字经过（或终止于）该节点的子树。
   • newNode(): 创建一个新节点，初始化子节点指针为 0，计数为 0。
   • init(): 初始化 Trie，通常创建一个根节点。
   • add(x, t): 插入或删除数字 x。t=1 为插入，t=-1 为删除。从根节点开始，按 x 的二进制位从高到低遍历。沿着对应的子节点路径前进，如果节点不存在则在插入时创建。将路径上所有节点的 cnt 值增加 t。
   • query(x): 查询 Trie 中与 x 异或值最大的数对应的异或结果。从根节点开始，按 x 的二进制位从高到低遍历 (例如从第 29 位到第 0 位，对于 30 位整数)。在第 i 位，x 的位是 d = (x >> i) & 1。我们希望 Trie 中的路径在这一位是 d ^ 1 (相反的位)，这样异或结果的第 i 位就是 1。检查 trie[o][d ^ 1] 是否存在且其计数 cnt 大于 0。如果可以走相反位路径，就走这条路，并将结果 ans 的第 i 位置为 1 (ans |= (1 << i))。否则，只能走相同位 d 的路径。更新当前节点 o 为选择的子节点。继续下一位。

时间复杂度

• 总共 n 次 add (插入) 操作，最多 n 次 add (删除) 操作，以及 n 次 query 操作。
• 每次 Trie 操作（插入、删除、查询）的时间复杂度是 $O(\log A_{\max})$，其中 $A_{\max}$ 是数组中元素的最大值 (这里是 $10^9$，大约需要 30 位)。
• 总时间复杂度是 $O(N \log A_{\max})$。

空间复杂度

• 存储数组 a: $O(N)$。
• Trie 的空间复杂度：每个数字插入最多创建 $\log A_{\max}$ 个新节点。总共 $N$ 个数字，所以 Trie 的节点数是 $O(N \log A_{\max})$。每个节点存储 2 个指针和 1 个计数器。
• 总空间复杂度是 $O(N \log A_{\max})$。代码中预分配了 N * 31 大小的空间，是足够的。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

// Trie 树节点的最大数量预估 N * log(MaxVal)
// 2e5 * 30 approx 6e6. N = 200000 * 31 足够
constexpr int N = 200000 * 31; 

int tot; // 当前 Trie 中节点的总数 (用于分配新节点 ID)

// trie[node_id][0/1] 存储节点 node_id 的左/右子节点 ID (0 代表不存在)
int trie[N][2]; 
// cnt[node_id] 存储有多少个数字经过了节点 node_id
int cnt[N]; 

// 创建一个新的 Trie 节点
int newNode() {
    int x = ++tot; // 获取新的节点 ID
    trie[x][0] = trie[x][1] = 0; // 初始化子节点为空
    cnt[x] = 0; // 初始化计数为 0
    return x;
}

// 初始化 Trie 树
void init() {
    tot = 0; // 重置节点计数器
    newNode(); // 创建根节点 (ID 为 1)
}

// 向 Trie 中添加或删除数字 x
// t = 1 表示添加, t = -1 表示删除
void add(int x, int t) {
    int o = 1; // 从根节点开始
    // 从最高位 (29) 向最低位 (0) 遍历 x 的二进制位
    for (int i = 29; i >= 0; i--) {
        // 获取 x 的第 i 位 (0 或 1)
        int bit = (x >> i) & 1;
        // p 是指向下一个子节点的引用
        int &p = trie[o][bit];
        // 如果子节点不存在 (p == 0)，并且是添加操作 (t == 1)，则创建新节点
        if (!p) {
            // 注意：不能仅在 t=1 时创建。如果删除时路径不存在则有问题。
            // 逻辑应该是如果不存在就创建，然后更新计数。
            // 但在此题中，保证了删除的数一定存在，所以这样写也可以。
            // 更健壮的写法是总检查并创建（如果不存在）。
             if (t == 1) p = newNode();
             else assert(false); // 如果删除时节点不存在，说明逻辑有误
            // 修正：不论 t=1 还是 t=-1，如果 p=0，说明路径有问题，应该总能找到路径
            // 正确逻辑：确保 p 存在，然后更新计数
            // if (!p) { p = newNode(); } // 应该总能创建或找到路径
        }
         if (!p) p = newNode(); // 创建缺失节点，确保路径完整
        o = p; // 移动到子节点
        cnt[o] += t; // 更新经过该节点的数字计数
    }
}

// 查询 Trie 中与 x 异或值最大的结果
int query(int x) {
    int o = 1; // 从根节点开始
    int ans = 0; // 存储最大异或结果
    // 从最高位 (29) 向最低位 (0) 遍历
    for (int i = 29; i >= 0; i--) {
        int d = (x >> i) & 1; // x 的当前位
        // 尝试走与 d 相反的路径 (d ^ 1)
        // 条件：相反路径的子节点存在 (trie[o][d ^ 1] != 0)
        //       并且该子树中有数字 (cnt[trie[o][d ^ 1]] > 0)
        if (trie[o][d ^ 1] && cnt[trie[o][d ^ 1]] > 0) { 
            d ^= 1; // 选择相反路径
            ans |= (1 << i); // 将结果的第 i 位置为 1
        }
        // 否则，只能走与 d 相同的路径
        // assert(trie[o][d] && cnt[trie[o][d]] > 0); // 必须存在路径，因为 x 自身在树中（如果查询前已添加）
        // 移动到选择的子节点
         if (!trie[o][d] || cnt[trie[o][d]] == 0) {
             // 如果连相同路径都没有或为空，说明Trie为空或逻辑出错
             // 对于本题的用法（查询前刚插入a[i]），这种情况不应发生
             // 但为健壮性，可以返回当前ans
             break; 
         }
        o = trie[o][d]; 
    }
    return ans;
}

// 处理单个测试用例的函数
void solve() {
    int n; // 数组长度
    long long k_ll; // k 可能较大，先用 long long 读入
    std::cin >> n >> k_ll;
    int k = k_ll; // 转为 int，因为数值本身在 int 范围内

    init(); // 初始化 Trie

    std::vector<int> a(n); // 存储输入数组
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int ans = n + 1; // 初始化答案为一个不可能的值

    // 双指针：i 是右端点，j 是左端点
    for (int i = 0, j = 0; i < n; i++) {
        add(a[i], 1); // 将 a[i] 加入当前窗口 [j..i] 的 Trie 中

        // 检查新加入的 a[i] 是否使得窗口 [j..i] 变得美丽
        // 通过查询 a[i] 与窗口中元素的最大异或值是否 >= k
        while (j <= i && query(a[i]) >= k) {
            // 如果条件满足，则子数组 a[j..i] 是美丽的
            // 更新最短长度
            ans = std::min(ans, i - j + 1);
            // 尝试缩小窗口：从左边移除 a[j]
            add(a[j], -1);
            // 左指针右移
            j++;
            // 继续检查缩小后的窗口是否仍然满足 query(a[i]) >= k
        }
    }

    // 如果 ans 仍然是初始值 n + 1，说明没有找到美丽的子数组
    if (ans > n) {
        ans = -1;
    }
    // 输出结果
    std::cout << ans << "\n";
}

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve();
    }

    return 0; // 程序正常结束
}