题意

给定一个非负整数数组 $a$
对每个长度至少为 $2$ 的子数组，定义其权值为：子数组内两两异或值最小值
即 b ⊂ a [ l , r ] , w ( b ) = min ⁡ l ≤ i < j ≤ r { a i ⨁ a j } b \subset a[l, r], \quad w(b) = \min_{l \leq i < j \leq r} \{a_i \bigoplus a_j\} b⊂a[l,r],w(b)=minl≤i<j≤r​{ai​⨁aj​}

求出所有子数组中权值第 $k$ 小的权值

思路

我们可以先二分答案 $mid$，并且快速统计有多少个子数组的权值 $\le mid$，记为 $cnt$，如果 $cnt\ge k$，说明答案可能比 $mid$ 更小，否则说明答案一定比 $mid$ 更大

问题在于如何快速统计 $cnt$？ 注意到其实随着子数组越大（越长），那么其权值一定是非递增的，也就是说更大的子数组会有更大的可能性满足权值 $w\le mid$

基于上述的观察，我们考虑先枚举区间的右端点 $rp$，我们要选择最大的 $lp$，使得 $a[lp,rp]$ 里， 任意一个右端点在 $rp$ 的子数组，其权值都大于 $mid$，也即是 $a[lp,rp]$ 里任意两两的异或权值都大于 $mid$，等价于两两异或的最小值大于 $mid$

又由于我们是从小到大枚举 $rp$ 的，那么上一轮的 $rp-1$ 就对应着其极大的 $lp$，如果 $lp$ 再小（即子数组更长），那么就会破坏上面的约束，使得最小值小于等于 $mid$。

因此新加入 $a_{rp}$ 时，我们只需要在 $01Trie$ 上对 $a_{rp}$ 查询异或最小值（因为前面 $[lp,rp-1]$ 两两异或值都符合要求），不难发现，我们的 $lp$ 是非递减的，这是一个双指针的过程。

对于一对极大的 $[lp,rp]$，右端点在 $rp$ 的权值小于等于 $mid$ 的子数组数量为 $lp-1$，即左端点的选择范围是：$[1,lp-1]$

当 $lp$ 右移时（删除某些 $a_{lp}$），我们只需要在 $01Trie$ 上擦除这些值即可

这样子就在 $O(n\log A)$ 下快速统计出了权值小于等于 $mid$ 的子数组数量

总体时间复杂度：$O(n{\log }^{2}A)$

注意每次二分都要清空 $Trie$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;const int N = 100005;struct node{int son[2];int cnt;int idx;
}tree[N * 32];int tot;void clear(){fore(i, 0, tot + 1){tree[i].cnt = tree[i].idx = tree[i].son[0] = tree[i].son[1] = 0;}tot = 0;
}void insert(int x, int i){int now = 0;for(int i = 29; i >= 0; --i){int ch = (x >> i & 1);if(!tree[now].son[ch])tree[now].son[ch] = ++tot;now = tree[now].son[ch];++tree[now].cnt;}tree[now].idx = i;
}std::pair<int, int> query(int x){ //return [mn, idx]int res = 0;int now = 0;for(int i = 29; i >= 0; --i){int ch = (x >> i & 1);int to = tree[now].son[ch];if(to && tree[to].cnt){now = to;}else{res |= (1 << i);now = tree[now].son[ch ^ 1];}}return {res, tree[now].idx}; //返回异或最小值和产生的下标i
}void erase(int x){int now = 0;for(int i = 29; i >= 0; --i){int ch = (x >> i & 1);now = tree[now].son[ch];--tree[now].cnt;}
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){int n;ll k;std::cin >> n >> k;std::vector<int> a(n + 1);fore(i, 1, n + 1) std::cin >> a[i];ll ans = 0;ll l = 0, r = 2e9;while(l <= r){clear();ll mid = l + r >> 1;int lp = 1, rp = 2;ll cnt = 1ll * n * (n - 1) / 2;;insert(a[1], 1);while(rp <= n){while(true){if(lp == rp) break;auto [mn, i] = query(a[rp]);if(mn > mid) break;while(lp <= i){erase(a[lp]);++lp;}}if(lp < rp){cnt -= rp - lp; //减去权值大于mid的子数组数量}insert(a[rp], rp);++rp;}if(cnt >= k){ans = mid;r = mid - 1;}else l = mid + 1;}std::cout << ans << endl;clear();}return 0;
}