Lflame

【2016/1/9 考题】 最大异或和 可持久化Trie 整体取反

    题意 :    一个长为N的序列,支持两个操作:      

                A x:添加操作,表示在序列末尾添加一个数x,序列的长度N+1。               Q l r x:询问操作,你需要找到一个位置p,满足l<=p<=r,使得:

a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。 


     看到这道题感觉可以存后缀异或和,但是题目是要求在后面加数,后缀会发生变化 !   

     于是写了一个平方分割,等加数加到一定程度再重建Trie,但是时间很卡,只拿了70分 。

     

    正解 :

           将后缀转化为前缀 ! 即用可持久化Trie维护前缀异或和,然后用x进去贪心前,将x异或一下整个序列,这样便正确了 !


     

#include<iostream>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

using namespace std;


int read(int &x)

{

bool f=0; char t=getchar() ; x=0;

while(t<'0'||t>'9'){

if(t=='-')f=1;

if(t==EOF)return EOF ;

t=getchar() ;

}

while(t>='0'&&t<='9'){

x=(x<<1)+(x<<3)+t-'0' ;

t=getchar() ;

}

if(f)x=-x ;

return 0 ;

}


char get_c()

{

char t;

while((t=getchar())!=EOF){

if(!isspace(t))

break ;

}

return t;

}


struct node;

typedef node* tree;

struct node{

tree p[2] ;

int cnt ;

}nd[20000005];

int ndnum ;

tree root[600005] , null ;


inline tree news()

{

tree ret=&nd[++ndnum] ;

ret->p[0]=ret->p[1]=null ;

ret->cnt=0 ;

return ret ;

}


int n,m;

int A[600005] , q[55] , qnum=28;


void fenjie(int t)

{

for(int i=0;i<=28;++i)q[i]=0 ;

int now=28 ;

while(t){

q[now--]=(t&1) ;

t>>=1 ;

}

}


void add_it(tree s1,tree &s2,int dep=0)

{

s2=news() ;

*s2=*s1 ;

s2->cnt ++ ;

if(dep>=qnum)return ;

add_it(s1->p[q[dep+1]],s2->p[q[dep+1]],dep+1) ;

}


int query_it(tree s1,tree s2)

{

int ret=0 ;

for(int i=1;i<=qnum;++i){

int tcnt=s2->p[q[i]^1]->cnt-s1->p[q[i]^1]->cnt ;

ret<<=1 ;

if(tcnt){

ret++ ;

s1=s1->p[q[i]^1] , s2=s2->p[q[i]^1] ;

}

else{

s1=s1->p[q[i]] , s2=s2->p[q[i]] ;

}

}

return ret;

}


int main()

{

freopen("xor.in","r",stdin) ;

freopen("xor.out","w",stdout) ;

read(n) ; read(m) ;

null=&nd[++ndnum] ;

null->p[0]=null->p[1]=null ;

null->cnt=0 ;

root[0]=null ;

int sum=0 ;

for(int i=1;i<=n;++i){

read(A[i]) ;

sum^=A[i] ;

fenjie(sum) ;

add_it(root[i-1],root[i]) ;

}

for(int i=1;i<=m;++i){

char o=get_c();

if(o=='A'){

read(A[++n]) ;

sum^=A[n] ;

fenjie(sum) ;

add_it(root[n-1],root[n]) ;

}

if(o=='Q'){

int l,r,t ;

read(l) ; read(r) ; read(t) ;

t^=sum ;

fenjie(t) ;

int ans;

if((root[l-2<0?0:l-2]->cnt == root[r-1]->cnt))ans=t ; //(debug) 还有没路走的情况,那么答案就是t

else ans=query_it(root[l-2<0?0:l-2],root[r-1]) ;

printf("%d\n",ans) ;

}

}

return 0 ;

}


评论