侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【Trie】最大异或和

GabrielxD
2023-02-28 / 0 评论 / 0 点赞 / 430 阅读 / 1,002 字
温馨提示:
本文最后更新于 2023-02-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

3485. 最大异或和 - AcWing题库


给定一个非负整数数列 aa ,初始长度为 NN

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

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

注意:子数组可以为空。

输入格式

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

第二行包含 NN 个整数,其中第 ii 个为 aia_i

输出格式

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

数据范围

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

输入样例:

3 2
1 2 4

输出样例:

6

解题

方法一:Trie

思路

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

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

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

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

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

代码

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);
    }
}
0

评论区