题解：P17209 「DLESS-6」XOR and Your Problem

· · 题解

你说得对但是压位 Trie 神了。

考虑以 B 为块长分块。

对于两端在同一个块内的询问，用 Trie 暴力求出答案。时间复杂度为 \mathcal{O}(qB\log{V})。

对于两端在不同块内的询问，把它挂到询问区间覆盖的最靠左的整块上。对于每个整块，把挂着的询问按右端点从小到大排序。从整块左端点开始向右扫，把扫到的数插入 Trie 中，扫到对应询问右端点时，再暴力询问左边散块中的数。时间复杂度为 \mathcal{O}(qB\log{V}+\dfrac{n^2}{B}\log{V})。

取 B=\sqrt{n} 即可做到 \mathcal{O}((n+q)\sqrt{n}\log{V})。

考虑使用压位 Trie。将普通 Trie 改为 16 叉 Trie，预处理

mx_{S,i}=\arg\max\limits_{j\in S}(i\oplus j)

这样就可以 \mathcal{O}(1) 求出最优的儿子。

但是这样大概率会 TLE。考虑剪枝，在 Trie 内查询异或最大值时传入一个 cur，每次更新当前答案时，若更低的位全部取 1 依然 \leq cur 就提前终止。

这样常数很小。再卡一下空间就可以勉强冲过去了。

:::success[主要代码]

int n, q, a[MAXN], ans[MAXN], suf[MAXN];
int blLen, blCnt, lb[MAX_CNT], rb[MAX_CNT], blNum[MAXN];

struct Query {
    int id, l, r;
};

vector<Query> queries[MAX_CNT];

struct Trie {
    static const int MAXC = 8.8e5 + 5;
    int tot, son[MAXC][16];
    unsigned short mask[MAXC];
    unsigned char mx[1 << 16][16];

    void build() {
        for (int s = 1; s < (1 << 16); ++s) {
            int h = __builtin_ctz(s), t = s ^ (1 << h);
            for (int i = 0; i < 16; ++i) {
                if (!t) {
                    mx[s][i] = h;
                } else {
                    int v = mx[t][i];
                    mx[s][i] = (h ^ i) > (v ^ i) ? h : v;
                }
            }
        }
    }

    void init() {
        tot = mask[0] = 0;
    }

    void ins(int x) {
        int p = 0;
        for (int i = 28; i >= 4; i -= 4) {
            int b = x >> i & 15;
            if (!(mask[p] >> b & 1)) {
                mask[p] |= 1 << b;
                mask[son[p][b] = ++tot] = 0;
            }
            p = son[p][b];
        }
        int b = x & 15;
        mask[p] |= 1 << b;
    }

    int query(int x, int cur) {
        int res = 0, p = 0;
        for (int i = 28; i >= 0; i -= 4) {
            int b = x >> i & 15, v = mx[mask[p]][b];
            res |= (b ^ v) << i;
            if ((res | ((1 << i) - 1)) <= cur) return cur;
            if (!i) break;
            p = son[p][v];
        }
        return res;
    }
} T;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    rd(n, q);
    for (int i = 1; i <= n; ++i) rd(a[i]);

    T.build();

    blLen = sqrt(n);
    for (int i = 1, j = 1; j <= n; ++i) {
        lb[i] = j;
        rb[i] = min(j + blLen - 1, n);
        while (j <= rb[i]) blNum[j++] = i;
    }

    blCnt = blNum[n];
    for (int i = 1; i <= blCnt; ++i) {
        int r = rb[i];
        T.init();
        for (int l = r; l >= lb[i]; --l) {
            T.ins(a[l]);
            suf[l] = T.query(a[l], suf[l + 1]);
        }
    }

    for (int i = 1; i <= q; ++i) {
        int l, r;
        rd(l, r);

        if (blNum[l] == blNum[r]) {
            T.init();
            for (int j = l; j <= r; ++j) {
                T.ins(a[j]);
                ans[i] = T.query(a[j], ans[i]);
            }
        } else {
            ans[i] = suf[l];
            queries[blNum[l] + 1].push_back({i, l, r});
        }
    }

    for (int i = 2; i <= blCnt; ++i) {
        if (queries[i].empty()) continue;
        sort(queries[i].begin(), queries[i].end(), [&](const Query &lhs, const Query &rhs) {
            return lhs.r < rhs.r;
        });

        T.init();
        int mx = 0, mxr = queries[i].back().r;
        for (int j = lb[i], p = 0; j <= mxr; ++j) {
            T.ins(a[j]);
            mx = T.query(a[j], mx);
            while (p < queries[i].size() && queries[i][p].r == j) {
                auto [id, l, r] = queries[i][p];
                chkMax(ans[id], mx);
                for (int k = lb[i] - 1; k >= l; --k) ans[id] = T.query(a[k], ans[id]);
                ++p;
            }
        }
    }

    for (int i = 1; i <= q; ++i) wt(ans[i]);
    return 0;
}

:::