[数据结构与算法]2021杭电多校第一场 Xor sum 字典树

Xor sum

题意

一个长度为 $n$ 的数组，找到一个最短（长度相同选左边）的区间，使得区间所有数的异或和大于等于 $k$ 。

题解

• 用字典树维护数组的前缀和，并维护字典树上结点的子树对应的前缀数组下标的最大值，也就是插入前缀数组的时候，维护通过每个结点的下标最大值；
• 先把 $0$ 插入字典树，对应下标也为 $0$ ；
• 然后遍历前缀和，贪心的去在字典树上剪枝搜索，找和这个前缀和异或大于等于 $k$ 的最大下标。

代码

#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
#ifdef LOCAL
#include "Print.h"
#define de(...) W('[', #__VA_ARGS__,"] =", __VA_ARGS__)
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn], pre[maxn];
struct Trie {
    int son[maxn << 5][2], idx = 1;
    int idm[maxn << 5]; // 这个结点子树的区间下标最大值
    void insert(int x, int id) {
        int p = 1;
        for (int i = 30; ~i; --i) {
            int &s = son[p][x >> i & 1];
            if (!s) s = ++idx;
            p = s;
            idm[p] = max(idm[p], id);
        }
    }
    void query(int x, int k, int &ansl) {
        int p = 1;
        for (int i = 30; ~i; --i) {
            int s = x >> i & 1;
            if (k >> i & 1) {
                if (son[p][!s]) p = son[p][!s];
                else return;
            } else {
                if (son[p][!s]) ansl = max(ansl, idm[son[p][!s]]);
                p = son[p][s];
            }
        }
        ansl = max(ansl, idm[p]);
    }
    void clear() {
        rep(i, 1, idx) son[i][0] = son[i][1] = 0, idm[i] = 0;
        idx = 1;
    }
} Tr;
int case_Test() {
    Tr.clear();
    int n, k;
    scanf("%d%d", &n, &k);
    rep(i, 1, n) scanf("%d", &a[i]), pre[i] = pre[i - 1] ^ a[i];
    int L = -1, R = n + 1;
    Tr.insert(0, 0);
    rep(i, 1, n) {
        int ansl = -1;
        Tr.query(pre[i], k, ansl);
        if (ansl != -1 && i - ansl < R - L) L = ansl, R = i;
        Tr.insert(pre[i], i);
    }
    if (L == -1) puts("-1");
    else printf("%d %d\n", L + 1, R);
    return 0;
}
int main() {
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t start = clock();
#endif
    int _ = 1;
    scanf("%d", &_);
    while (_--) case_Test();
#ifdef LOCAL
    printf("Time used: %.3lfs\n", (double)(clock() - start) / CLOCKS_PER_SEC);
#endif
    return 0;
}