【Trie】最大异或和

题目

3485. 最大异或和 - AcWing题库

---

给定一个非负整数数列 $a$ ，初始长度为 $N$ 。

请在所有长度不超过 $M$ 的连续子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

输入格式

第一行包含两个整数 $N,M$ 。

第二行包含 $N$ 个整数，其中第 $i$ 个为 $a_i$ 。

输出格式

输出可以得到的子数组异或和的最大值。

数据范围

对于 $20\%$ 的数据， $1 \le M \le N \le 100$
对于 $50\%$ 的数据， $1 \le M \le N \le 1000$
对于 $100\%$ 的数据， $1 \le M \le N \le 10^5,0 \le a_i \le 2^{31}-1$

输入样例：

3 2
1 2 4

输出样例：

6

解题

方法一：Trie

思路

提到求一段连续区间（连续子数组）的和首先想到可以使用前缀和进行优化。

本题数据范围最大有 $10^5$ ，所以时间复杂度要控制在 $O(n\log{n})$ 之内，这样以来显然只能枚举子数组的一个端点。

枚举子数组的右端点 $r$ ，对于每个固定的右端点 $r$ 我们需要找到左端点 $l$ （$r - m + 1 \le l \le r$）使得 $a_l \oplus \dots \oplus a_r$ 最大，而之前我们构造了前缀和数组，所以 $a_l \oplus \dots \oplus a_r = s_r \oplus s_{l - 1}$ （$r - m \le l - 1 \le r - 1$）。这样以来我们就把问题从求一段数的异或和最大变成了求两个数的异或和最大，这个问题被转换为【Trie树】最大异或对。

因为要保证连续子数组长度不能超过 $m$ ，所以在之前Trie实现的基础上需要增加删除的操作，删除的操作也很好实现，只需要增加一个 cnts 数组用来记录以每个节点为根的子树中包括多少个点，插入和删除的时候操作该数组，查询的时候检查该数组，检查对应的子树节点数量来做出分支判断即可。

注意：在开始枚举之前，需要先把 $s[0]$ 先加入Trie中，因为 $l$ 是有可能取到下标 $0$ 的。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = (int) (1e5 + 10) * 31;
    static int[][] sons = new int[N][2];
    static int[] cnts = new int[N];
    static int idx = 0;
    
    // 插入: o = 1  删除 o = -1
    static void insert(int x, int o) {
        int p = 0;
        for (int i = 30; i >= 0; --i) {
            int curr = x >> i & 1;
            if (sons[p][curr] == 0) sons[p][curr] = ++idx;
            p = sons[p][curr];
            cnts[p] += o;
        }
    }
    
    static int query(int x) {
        int p = 0, res = 0;
        for (int i = 30; i >= 0; --i) {
            int curr = x >> i & 1;
            res <<= 1;
            if (cnts[sons[p][curr ^ 1]] == 0) p = sons[p][curr];
            else {
                ++res;
                p = sons[p][curr ^ 1];
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            s[i] = s[i - 1] ^ (int) in.nval;
        }
        int mx = 0;
        insert(s[0], 1);
        for (int i = 1; i <= n; ++i) {
            if (i - m - 1 >= 0) insert(s[i - m - 1], -1);
            mx = Math.max(mx, query(s[i]));
            insert(s[i], 1);
        }
        System.out.println(mx);
    }
}