【bzoj3261】【最大异或和】可持久化trie树+贪心-LMLPHP

[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=61705397

首先明确,若已知后缀异或和,及已知一些数和给出数异或,我们可以贪心。从最高位往低位找。eg:

给出数x:1000101

已知的一些数:(1)0010010 (2)1000001 (3)0100101

x的最高位已是1,所以只选(1)(3),次高位为0,所以选(3)

贪心明确了,那么该怎么快速的找到符合选项进一步筛选呢。我们想到,这个01串像字符串,是不是可以用字符串的知识呢?很明显想到trie树。对01串建trie树即可。

但是这道题。。。我们不可能每一次都用后缀和建一次trie树,很明显会T掉。然而就算对后缀异或和用上可持久化trie数,也是不行的,因为还会有在末尾加入的操作。怎么办呢。。。当一个思路卡住时,我们可以考虑略微改变思路。正所谓“失之毫厘,差之千里”。

如果可以维护前缀和就好了,可是前缀和可以转后缀和就好了。显然, 一般意义下,a[n]-a[i]即为不含i的后缀和,而异或也有交换律,a[n]^a[i]即为不含i的后缀异或和(此a非彼a)。那么每次只需从区间[l,r]中选前缀异或和与x^a[n]的最大值即可。

可持久化trie树的方式和可持久化线段树基本上是一致的,对每一个节点记录一个cnt,与前面对应的点相减,不为零即区间内有这个点。

代码(特别注意前缀转后缀时的区间对应关系,通常要-1,这里l要-2,但还要注意数组不能访问到负数,特判一下)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int N=600000+5; struct Node{
Node *s0,*s1;
int sum;
}*root[N],*null,pool[N*50],*tail=pool;
int n,m,a[N],ans; Node *newnode(){
Node *rt=++tail;
rt->s0=rt->s1=null;
rt->sum=0;
return rt;
}
void insert(Node *&ndn,Node *ndp,int pos,int val){
ndn=newnode();
ndn->s0=ndp->s0,ndn->s1=ndp->s1;
ndn->sum=ndp->sum+1;
if(pos==-1) return ;
bool d=((val>>pos)&1);
if(d==0) insert(ndn->s0,ndp->s0,pos-1,val);
else insert(ndn->s1,ndp->s1,pos-1,val);
}
void query(Node *ndn,Node *ndp,int pos,int val){
if(pos==-1) return ;
int ls=ndn->s0->sum - ndp->s0->sum;
int rs=ndn->s1->sum - ndp->s1->sum;
bool d=((val>>pos)&1);
if(d==0){
if(rs){
ans=ans^(1<<pos);
query(ndn->s1,ndp->s1,pos-1,val);
}
else if(ls){
query(ndn->s0,ndp->s0,pos-1,val);
}
}
if(d==1){
if(ls){
query(ndn->s0,ndp->s0,pos-1,val);
}
else if(rs){
ans=ans^(1<<pos);
query(ndn->s1,ndp->s1,pos-1,val);
}
}
}
int main(){
null=++tail;
null->s0=null->s1=null;
null->sum=0;
root[0]=null; scanf("%d%d",&n,&m);
int aa;
for(int i=1;i<=n;i++){
scanf("%d",&aa);
a[i]=a[i-1]^aa;
insert(root[i],root[i-1],31,a[i]);
}
char opt[2];
int l,r,x;
while(m--){
scanf("%s",opt);
if(opt[0]=='A'){
scanf("%d",&x);
n++;
a[n]=a[n-1]^x;
insert(root[n],root[n-1],31,a[n]);
}
else{
scanf("%d%d%d",&l,&r,&x);
ans=x^a[n];
if(l-2>=0) query(root[r-1],root[l-2],31,x^a[n]);
else query(root[r-1],root[0],31,x^a[n]);
printf("%d\n",ans);
}
}
return 0;
}

总结:

1、对字符串工具的灵活转化。trie树可以将前缀一样的东西合并起来,既省时又省空间。

2、转变思路。常常反个面想就会得到不一样的效果。正所谓“阴阳相生”、“否极泰来”,正反面常常可以互通。有一句话叫做“正难即反”。

05-11 22:21
查看更多