洛谷题单指南-字符串-P4735 最大异或和

原题链接：https://www.luogu.com.cn/problem/P4735

题意解读：已知长度为n的数组a[]，要在l~r范围找到一个p，使得a[p]^a[p+1]^...^a[n]^x最大，求这个最大的异或值。

解题思路：

1、利用前缀和将问题转化

设s[]是a[]的前缀异或数组，要计算a中一段范围l~r的异或，可以借助于s

由于s[r] = a[0]^a[1]^...a[l-1]^a[l]^...^a[r]，s[l-1] = a[0]^a[1]^...^a[l-1]

因此s[r] ^ s[l-1] = a[l]^a[l+1]^...^a[r]

对于a[p]^a[p+1]^...^a[n]^x，可以转化为s[n]^x^s[p-1]，即问题转化为在s[l-1]~s[r-1]范围内找到一个s[p-1]使得s[n]^x与其异或值最大。

要计算与一个数异或最大的值，可以借助于Trie树，但是这里限制条件是要在一个范围内找到与某个数异或的最大值，需要引入一种新的数据结构-持久化Trie树。

2、持久化Trie树介绍

所谓持久化Trie，一般用于01Trie，是指对每一个数字进行加入trie操作时，都建立一个新的根节点，从该根节点可以查找到之前添加的所有的数，具体如何实现呢？我们以2 6 4 3 为例进行Trie添加操作：

添加的过程有以下特点：

• 每添加一个数s[i]，都建立一个根节点root[i]，从root[i]可以查找到s[1]~s[i]所有数
• 当添加s[i]时，对于s[i]的每一个二进制位都新建立节点，对于不在s[i]中的二进制位，复制前一个根的节点
• 如添加6时，trie[6][0]=trie[1][0]是复制前一个根节点，而trie[6][1]=7是新建节点

查找的过程：

要在L~R范围内查找与x异或最大的结果，可以在根为root[R]中去找1~R范围的数，同时用一个maxid[]来记录Trie树中每一个节点所经过的数的最大id，这样在查找最大异或值时，只需要判断相反位节点存在且maxid[]>=L即说明是L~R范围的数，不存在则走相同位的节点。

Trie树操作核心代码：

//将s[id]添加到持久化Trie
void add(int id)
{
    root[id] = ++idx; //创建当前根节点
    int cur = root[id]; //当前根
    int pre = root[id - 1]; //前一个根
    for(int i = 23; i >= 0; i--)
    {
        int v = s[id] >> i & 1;
        trie[cur][!v] = trie[pre][!v]; //相反位复制上一个根
        trie[cur][v] = ++idx; //对s[i]每个二进制位新建节点
        maxid[cur] = id; //更新maxid
        cur = trie[cur][v], pre = trie[pre][v]; //根沿着s[i]的二进制位往下走
    }
    maxid[cur] = id; //更新maxid
}

//在l~r范围内查找与val异或的最大值
int find(int l, int r, int val)
{
    int res = 0;
    int u = root[r]; //根
    for(int i = 23; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(maxid[trie[u][!v]] >= l) //如果相反位的节点存在且最大编号>=l
        {
            u = trie[u][!v];
            res = res * 2 + 1; //异或后1对结果的贡献
        }
        else
        {
            u = trie[u][v];
            res = res * 2; //异或后0对结果的贡献
        }
    }
    return res;
}

3、最终问题求解

第一步：计算前缀异或

第二步：建立持久化Trie

第三步：范围查找最大异或值

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 600005, M = N * 24;
int s[N]; //前缀异或数组
int root[N]; //所有版本trie的根节点
int trie[M][2], idx, maxid[M]; //trie树，maxid[]保存经过某个节点的数的最大s编号
int n, m;
char op;
int l, r, x;

//将s[id]添加到持久化Trie
void add(int id)
{
    root[id] = ++idx; //创建当前根节点
    int cur = root[id]; //当前根
    int pre = root[id - 1]; //前一个根
    for(int i = 23; i >= 0; i--)
    {
        int v = s[id] >> i & 1;
        trie[cur][!v] = trie[pre][!v]; //相反位复制上一个根
        trie[cur][v] = ++idx; //对s[i]每个二进制位新建节点
        maxid[cur] = id; //更新maxid
        cur = trie[cur][v], pre = trie[pre][v]; //根沿着s[i]的二进制位往下走
    }
    maxid[cur] = id; //更新maxid
}

//在l~r范围内查找与val异或的最大值
int find(int l, int r, int val)
{
    int res = 0;
    int u = root[r]; //根
    for(int i = 23; i >= 0; i--)
    {
        int v = val >> i & 1;
        if(maxid[trie[u][!v]] >= l) //如果相反位的节点存在且最大编号>=l
        {
            u = trie[u][!v];
            res = res * 2 + 1; //异或后1对结果的贡献
        }
        else
        {
            u = trie[u][v];
            res = res * 2; //异或后0对结果的贡献
        }
    }
    return res;
}

int main()
{
    cin >> n >> m;
    maxid[0] = -1; //不存在的节点maxid=-1，便于find中比较
    add(0); //第一个数添加0，使得便于区间计算
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] = s[i - 1] ^ s[i]; //计算前缀异或
        add(i); //添加到持久化Trie
    } 
    while(m--)
    {
        cin >> op;
        if(op == 'A')
        {
            cin >> x;
            s[n + 1] = s[n] ^ x;
            n++;
            add(n);
        }
        else
        {
            cin >> l >> r >> x;
            cout << find(l - 1, r - 1, x ^ s[n]) << endl;
        }
    }
}