企业官网建设流程全解析

【题目来源】

AcWing：256. 最大异或和 - AcWing题库

【题目描述】

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

有M MM个操作，有以下两种操作类型：

1. A x：添加操作，表示在序列末尾添加一个数x xx，序列的长度N NN增大1 11。
2. Q l r x：询问操作，你需要找到一个位置p pp，满足l ≤ p ≤ r l≤p≤rl≤p≤r，使得：KaTeX parse error: Undefined control sequence: \ at position 5: a[p]\̲ ̲xor\ a[p+1]\ xo…最大，输出这个最大值。

【输入】

第一行包含两个整数N NN，M MM，含义如问题描述所示。

第二行包含N NN个非负整数，表示初始的序列A AA。

接下来M MM行，每行描述一个操作，格式如题面所述。

【输出】

每个询问操作输出一个整数，表示询问的答案。

每个答案占一行。

【输入样例】

5 5 2 6 4 3 6 A 1 Q 3 5 4 A 4 Q 5 7 0 Q 3 6 6

【输出样例】

4 5 6

【核心思想】

1. 问题分析：给定一个动态增长的非负整数序列，支持在末尾添加元素和区间查询操作。查询要求在区间[ l , r ] [l, r][l,r]内找到一个位置p pp，使得a [ p ] ⊕ a [ p + 1 ] ⊕ … ⊕ a [ N ] ⊕ x a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus xa[p]⊕a[p+1]⊕…⊕a[N]⊕x最大。利用前缀异或和转化后，问题变为：在区间[ l − 1 , r − 1 ] [l-1, r-1][l−1,r−1]内找到一个前缀异或和s [ p − 1 ] s[p-1]s[p−1]，使得s [ p − 1 ] ⊕ ( s [ N ] ⊕ x ) s[p-1] \oplus (s[N] \oplus x)s[p−1]⊕(s[N]⊕x)最大。这是一个**可持久化字典树（Persistent Trie）**问题，核心在于维护历史版本以支持区间限制下的最大异或查询。

2. 算法选择：

   • 前缀异或和转化：令s [ i ] = a [ 1 ] ⊕ a [ 2 ] ⊕ … ⊕ a [ i ] s[i] = a[1] \oplus a[2] \oplus \ldots \oplus a[i]s[i]=a[1]⊕a[2]⊕…⊕a[i]，则a [ p ] ⊕ … ⊕ a [ N ] = s [ p − 1 ] ⊕ s [ N ] a[p] \oplus \ldots \oplus a[N] = s[p-1] \oplus s[N]a[p]⊕…⊕a[N]=s[p−1]⊕s[N]，查询转化为求max ⁡ l − 1 ≤ p − 1 ≤ r − 1 { s [ p − 1 ] ⊕ C } \max_{l-1 \leq p-1 \leq r-1} \{s[p-1] \oplus C\}maxl−1≤p−1≤r−1​{s[p−1]⊕C}，其中C = s [ N ] ⊕ x C = s[N] \oplus xC=s[N]⊕x
   • 可持久化字典树（Persistent Trie / 主席树）：每个版本对应一个前缀异或和集合，通过路径复制实现O ( log ⁡ V ) O(\log V)O(logV)的版本创建（V VV为数值范围）
   • 贪心高位优先：在字典树上从高位到低位优先走与目标值当前位不同的分支，使异或结果最大

3. 关键步骤：

   • 前缀异或和预处理：s [ i ] = s [ i − 1 ] ⊕ a i s[i] = s[i-1] \oplus a_is[i]=s[i−1]⊕ai​，其中s [ 0 ] = 0 s[0] = 0s[0]=0
   • 问题转化：查询Q ( l , r , x ) Q(l, r, x)Q(l,r,x)等价于在集合{ s [ 0 ] , s [ 1 ] , … , s [ r − 1 ] } \{s[0], s[1], \ldots, s[r-1]\}{s[0],s[1],…,s[r−1]}中，找到下标≥ l − 1 \geq l-1≥l−1的元素与C = s [ N ] ⊕ x C = s[N] \oplus xC=s[N]⊕x异或最大
   • 可持久化字典树构建：
     • 第i ii个版本r o o t [ i ] root[i]root[i]包含前缀异或和s [ 0 ] , s [ 1 ] , … , s [ i ] s[0], s[1], \ldots, s[i]s[0],s[1],…,s[i]
     • 插入s [ i ] s[i]s[i]时，从高位到低位（第23 2323位到第0 00位），复制旧版本未修改的分支，创建新节点存储当前位
     • 每个节点维护m a x _ i d max\_idmax_id：以该节点为根的子树中最大的下标编号
   • 查询操作：
     • 从版本r o o t [ r − 1 ] root[r-1]root[r−1]的根节点出发（保证只考虑下标≤ r − 1 \leq r-1≤r−1的元素）
     • 从高位到低位贪心：若与C CC当前位不同的分支中存在m a x _ i d ≥ l − 1 max\_id \geq l-1max_id≥l−1的节点，则走该分支
     • 否则走相同分支，确保所选元素下标≥ l − 1 \geq l-1≥l−1
   • 添加操作：序列长度N NN增加，计算新的s [ N ] s[N]s[N]，基于r o o t [ N − 1 ] root[N-1]root[N−1]创建新版本r o o t [ N ] root[N]root[N]

4. 时间/空间复杂度：

   • 时间复杂度：O ( ( N + M ) log ⁡ V ) O((N + M) \log V)O((N+M)logV)，每次插入和查询均为O ( log ⁡ V ) O(\log V)O(logV)，V VV为数值范围（本题中V = 2 24 V = 2^{24}V=224，故为O ( 24 ) O(24)O(24)）
   • 空间复杂度：O ( ( N + M ) log ⁡ V ) O((N + M) \log V)O((N+M)logV)，每个版本新增O ( log ⁡ V ) O(\log V)O(logV)个节点

5. 可持久化字典树的核心思想：

   • 版本化历史快照：每个版本r o o t [ i ] root[i]root[i]保存前i ii个前缀异或和的完整字典树结构，通过路径复制实现O ( log ⁡ V ) O(\log V)O(logV)的空间增量
   • 路径复制策略：插入新值时只修改从根到叶子的一条路径上的节点，其余分支直接引用旧版本节点，实现空间高效的历史版本维护
   • 下标约束的贪心查询：利用m a x _ i d max\_idmax_id数组在遍历过程中实时判断某个分支是否存在满足下标限制的元素，将区间限制转化为版本选择 + 分支可行性判断
   • 前缀异或的区间转化：将区间异或查询通过前缀和差分转化为单点查询，使得字典树可以处理动态区间最大异或问题
   • 适用于动态数组的区间最大/最小异或查询、带历史版本的集合查询类问题

【算法标签】

#主席树

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=600005,M=N*25;// N: 最大序列长度; M: 字典树最大节点数intn,m;// n: 序列长度; m: 操作次数ints[N];// s[i]: 前缀异或和，s[i] = a[1] xor a[2] xor ... xor a[i]inttr[M][2];// tr[p][0/1]: 字典树节点 p 的左右子节点（0/1 分支）intmax_id[M];// max_id[p]: 以节点 p 为根的子树中，最大的下标编号introot[N];// root[i]: 第 i 个版本的字典树根节点intidx;// idx: 字典树节点计数器voidinsert(inti,intk,intp,intq)// 可持久化字典树插入，i: 下标，k: 当前位，p: 旧版本节点，q: 新版本节点{if(k<0)// 已处理完所有位（到达叶子）{max_id[q]=i;// 记录该路径对应的最大下标return;}intv=s[i]>>k&1;// 取出 s[i] 的第 k 位if(p)// 如果旧版本存在，复制旧版本的另一分支tr[q][v^1]=tr[p][v^1];tr[q][v]=++idx;// 创建新版本当前位的子节点insert(i,k-1,tr[p][v],tr[q][v]);// 递归插入下一位max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);// 更新当前节点的最大下标}intquery(introot,intC,intL)// 查询操作，root: 版本根节点，C: 目标异或值，L: 下标下限{intp=root;// 从版本根节点开始for(inti=23;i>=0;i--)// 从高位到低位贪心，优先走与 C 当前位不同的分支{intv=C>>i&1;// 取出 C 的第 i 位if(max_id[tr[p][v^1]]>=L)// 如果异或分支（v^1）中存在下标 >= L 的数p=tr[p][v^1];// 走异或分支，使结果更大elsep=tr[p][v];// 否则走相同分支}returnC^s[max_id[p]];// 返回 C 与最优前缀异或和的结果}intmain(){cin>>n>>m;// 读入初始序列长度和操作次数max_id[0]=-1;// 初始化空节点的 max_id 为 -1root[0]=++idx;// 创建第 0 个版本（空序列）insert(0,23,0,root[0]);// 插入 s[0] = 0for(inti=1;i<=n;i++)// 读入初始序列并建立可持久化字典树{intx;// x: 当前读入的数cin>>x;s[i]=s[i-1]^x;// 计算前缀异或和root[i]=++idx;// 创建第 i 个版本insert(i,23,root[i-1],root[i]);// 基于上一版本插入 s[i]}charop;// op: 操作类型intl,r,x;// l, r: 区间; x: 操作数值while(m--)// 循环处理 m 次操作{cin>>op;// 读入操作类型if(op=='A')// 操作 A：在序列末尾添加一个数{cin>>x;n++;// 序列长度加一s[n]=s[n-1]^x;// 更新前缀异或和root[n]=++idx;// 创建新版本insert(n,23,root[n-1],root[n]);// 基于上一版本插入}else// 操作 Q：询问操作{cin>>l>>r>>x;// 查询版本 root[r-1] 中，满足下标 >= l-1 且与 (s[n]^x) 异或最大的值cout<<query(root[r-1],s[n]^x,l-1)<<endl;}}return0;}

【运行结果】

5 5 2 6 4 3 6 A 1 Q 3 5 4 4 A 4 Q 5 7 0 5 Q 3 6 6 6