首页 > 代码库 > 【bzoj3281】最大异或和 可持久化Trie树

【bzoj3281】最大异或和 可持久化Trie树

题目描述

给定一个非负整数序列 {a},初始长度为 N。       
有M个操作,有以下两种操作类型:
1、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。
2、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:
a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。  

 

 

输入

 

第一行包含两个整数 N  ,M,含义如问题描述所示。   
第二行包含 N个非负整数,表示初始的序列 A 。 
接下来 M行,每行描述一个操作,格式如题面所述。   

 

 

输出

 

假设询问操作有 T个,则输出应该有 T行,每行一个整数表示询问的答案。

 

 

样例输入

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


题解

可持久化Trie树

由于x xor x=0,所以$a_p\oplus a_{p+1}\oplus \cdots\oplus a_{n-1}\oplus a_n\oplus x=(a_1\oplus a_2\oplus\cdots\oplus a_{p-2}\oplus a_{p-1})\oplus(a_1\oplus a_2\oplus\cdots\oplus a_{n-1}\oplus a_{n})\oplus x$

维护一个前缀异或和,则这里的sum[n] xor x是已知的,只要求出是这个值最大的sum[p-1]。

因为100000(2)>011111(2),所以可以把前缀和放到可持久化Trie树中,然后贪心求解。

这里需要注意的是l可能等于1,会使用到sum[0],而建立可持久化Trie树时就要用到root[-1],所以把整个数组向右平移一位。

#include <cstdio>#include <algorithm>#define N 600010using namespace std;int sum[N] , next[N * 20][2] , si[N * 20] , tot , root[N];char str[5];int insert(int x , int v){	int tmp , y , i;	bool t;	tmp = y = ++tot;	for(i = 1 << 24 ; i ; i >>= 1)	{		next[y][0] = next[x][0] , next[y][1] = next[x][1] , si[y] = si[x] + 1;		t = v & i , x = next[x][t] , next[y][t] = ++tot , y = next[y][t];	}	si[y] = si[x] + 1;	return tmp;}int query(int x , int y , int v){	int ret = 0 , i;	bool t;	for(i = 1 << 24 ; i ; i >>= 1)	{		t = v & i;		if(si[next[y][t ^ 1]] - si[next[x][t ^ 1]]) ret += i , x = next[x][t ^ 1] , y = next[y][t ^ 1];		else x = next[x][t] , y = next[y][t];	}	return ret;}int main(){	int n , m , i , x , y , z;	scanf("%d%d" , &n , &m) , n ++ ;	for(i = 2 ; i <= n ; i ++ ) scanf("%d" , &x) , sum[i] = sum[i - 1] ^ x;	for(i = 1 ; i <= n ; i ++ ) root[i] = insert(root[i - 1] , sum[i]);	while(m -- )	{		scanf("%s%d" , str , &x);		if(str[0] == ‘A‘) n ++ , sum[n] = sum[n - 1] ^ x , root[n] = insert(root[n - 1] , sum[n]);		else scanf("%d%d" , &y , &z) , printf("%d\n" , query(root[x - 1] , root[y] , sum[n] ^ z));	}	return 0;}

 

 

【bzoj3281】最大异或和 可持久化Trie树