Codeforces Round 956 F. array-value 【01Trie查询异或最小值】

题意

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

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

思路

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

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

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

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

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

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

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

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

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

注意每次二分都要清空 $T r i e$

#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;
}