bzoj3261

xor有一个很重要的性质就是A xor B xor B=A
所以这道题求[l,r]中p,使a[p] xor a[p+1] xor ... xor a[N] xor x 最大
就是=最大化a[1] xor ……a[n] xor x xor a[1] xor a[2] xor ……a[p-1]
令b[i]=a[1] xor a[2] xor ……a[i]
则最大化b[p] xor b[n] xor X p∈[l-1,r-1]
抛开区间，求b[p] xor Y的最大值我们需要用到trie树
由于是区间修改，所以要求我们对trie进行可持久化
类比主席树，我们对每个i都建立一棵trie树，不同的节点增开空间
在区间询问的时候，如果两棵树指向同一个节点，说明这一位上的值是不能取的，否则就按trie的贪心做
感觉可持久化就是对历史信息尽可能的保留，对新的值新开空间

 var son:array[-..,..] of longint;

     i,t,x,l,r,n,m:longint;

     b,root:array[-..] of longint;

     ch:char;

 procedure add(j,x:longint);

   var i,a,b,y:longint;

   begin

     a:=root[j-];

     b:=root[j];

     for i:= downto  do

     begin

       y:=x and ( shl i);

       if y> then y:=;

       inc(t);

       son[b,y]:=t;  //类比主席树

       son[b,-y]:=son[a,-y];

       a:=son[a,y];

       b:=son[b,y];

     end;

   end;

 function ask(l,r,x:longint):longint;

   var y,i,a,b:longint;

   begin

     a:=root[l];

     b:=root[r];

     ask:=;

     for i:= downto  do

     begin

       y:=x and ( shl i);

       if y> then y:=;

       if (son[b,-y]=) or (son[b,-y]=son[a,-y]) then  //判断这位在区间内是否存在

       begin

         a:=son[a,y];

         b:=son[b,y];

       end

       else begin

         ask:=ask+ shl i;

         a:=son[a,-y];

         b:=son[b,-y];

       end;

     end;

   end;

 begin

   readln(n,m);

   b[]:=;

   t:=;

   root[]:=;

   x:=;

   for i:= downto  do

   begin

     inc(t);

     son[x,]:=t;

     x:=t;

   end;

   for i:= to n do

   begin

     read(x);

     b[i]:=b[i-] xor x;

     inc(t);

     root[i]:=t;

     add(i,b[i]);

   end;

   readln;

   for i:= to m do

   begin

     read(ch);

     if ch='A' then

     begin

       readln(x);

       inc(n);

       b[n]:=b[n-] xor x;

       inc(t);

       root[n]:=t;

       add(n,b[n]);

     end

     else begin

       readln(l,r,x);

       x:=x xor b[n];

       writeln(ask(l-,r-,x));

     end;

   end;

 end.

巴特西

bzoj3261

最新文章

热门文章