题解 P4735 【最大异或和】
前面几篇题解已经说了,正解是可持久化Trie(字典树).
之所以打算写一下题解,是因为我用的其他题解中没有的自带大常数的指针做法,并且这个题还有两三个重要的坑点技巧...
思路(自己+借鉴):
首先要对位运算较为熟悉,一定要知道异或运算的特性,即如下
s[1] = a[0] xor a[1]
s[p] = s[p - 1] xor a[p]
a[p] xor a[p + 1] xor ... xor a[N] xor x = s[p - 1] xor s[N] xor x如果还不懂,并且有一点图论基础的话,可以先做P4551 最长异或路径来练习,不需要可持久化思想.
那么在序列末尾添加数字时,先让n=n + 1,维护s数组,并向Trie中插入s[n]的24位二进制数,前面用0填充.
其实这个题难点在于查询
根据位运算特性,有如下结论:
a[p] xor a[p + 1] xor ... xor a[N] xor x = s[p - 1] xor s[N] xor x
当l <= p <= r时,求p,使s[p - 1] xor s[N] xor x最大 如果没有l和r的限制,那么就和P4551求法相同,然而考虑右端r的限制,所以要用到可持久化思想.
可持久化Trie其实看起来不那么容易,其实很好写.只要在原Trie基础上,每次插入时,要用到的节点都新创建一个,再继承原来相同位置上的节点,这样就可以通过不同时期的根节点访问不同时期的Trie.
有了可持久化Trie,那么区间右端r的限制就解决了,只要搜索时从r-1开始搜索就行了.
现在再考虑左端l的限制,其实也思路和做法都比较简单,只需要在每个点上标记经过这个节点的最大的数.具体求法就是在插入时,标记插入路径上的点全为当前插入的s数组的下标就行了.因为插入时下标是越来越大的,所以就不用考虑标记的是否为最大的数了.
下面考虑查询如何搜索
那么在搜索时,若只有0的下标为0,搜索第r-1个根,从最高位(第24位)开始,一直到0位,每次先看此位上异或大的子节点,是否存在且是否标记值>=l-1,若都成立,就让当前指针指向此此孩子,并让此次ans+=1<<此位,否则就检查另外一个子节点,条件都不成立,直接返回当前ans.
这个题还有几个技巧:
卡常: inline register 手写new节点函数 快读
还有就是一开始不能为空Trie树,需要科学插入一个0,第二个点有区间左端点l=1并且num异或0最大.
代码实现:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct node {
node *childs[2];
int symboln;
} * mainnodes[500001], nodes[13000001];
int mptr, nptr;
//mainnode的下标指针,nodes的下标指针
inline node *newnode(node *an, int s) {
++nptr;
nodes[nptr].childs[0]= an->childs[0], nodes[nptr].childs[1]= an->childs[1];
nodes[nptr].symboln= s;
return &nodes[nptr];
}
inline node *newnode(int s) {
++nptr;
nodes[nptr].childs[0]= nodes[nptr].childs[1]= NULL;
nodes[nptr].symboln= s;
return &nodes[nptr];
}
//newnode为手写new节点
inline void insert(int num) {
register node *lnode= newnode(mainnodes[mptr], mptr + 1);
//卡常,创建一个新的根节点继承原来的
mainnodes[++mptr]= lnode;
for(register int i= 24, ch; i + 1; --i) {
ch= num >> i & 1;
//位运算判断二进制下第i位是否为1
if(lnode->childs[ch])
lnode= lnode->childs[ch]= newnode(lnode->childs[ch], mptr);
else
lnode= lnode->childs[ch]= newnode(mptr);
//需要改变的节点要创建新的节点,原来存在还要继承原来的节点
}
return;
}
inline int find(int num, int l, int r) {
//此处l和r,在输入时已经都-1
register node *lnode= mainnodes[r];
int ans= 0;
for(register int i= 24, ch; i + 1; --i) {
ch= num >> i & 1;
if(lnode->childs[ch ^ 1] && lnode->childs[ch ^ 1]->symboln >= l)
lnode= lnode->childs[ch ^ 1], ans+= 1 << i;
//优先选择此位上异或为1的
//要满足标记值>=左端点-1
else if(lnode->childs[ch] && lnode->childs[ch]->symboln >= l)
lnode= lnode->childs[ch];
else
break;
}
return ans;
}
void init() {
register node *lnode= newnode(0);
mainnodes[0]= lnode;
for(register int i= 24; i + 1; --i) {
lnode->childs[0]= newnode(0);
lnode= lnode->childs[0];
}
//初始化,向起始的Trie树插入0
}
inline int read() {
static char c= getchar();
int a= 0;
while(c < '0' || c > '9') c= getchar();
while(c >= '0' && c <= '9') a= a * 10 + c - '0', c= getchar();
return a;
}
//快读卡常优化
int n, m, tmpx, tmpl, tmpr, xors[500001];
char tmpy;
int main() {
init();
n= read(), m= read();
for(register int i= 1; i <= n; i++) {
tmpx= read();
xors[i]= xors[i - 1] ^ tmpx;
//根据异或原理维护s(xors)数组
insert(xors[i]);
}
for(register int i= 0; i < m; i++) {
scanf(" %c", &tmpy);
if(tmpy == 'A') {
tmpx= read();
xors[n + 1]= xors[n] ^ tmpx;
insert(xors[++n]);
}
else {
tmpl= read(), tmpr= read(), tmpx= read();
printf("%d\n", find(xors[n] ^ tmpx, tmpl - 1, tmpr - 1));
}
}
return 0;
}