【BZOJ4260】Codechef REBXOR Trie树+贪心

【BZOJ4260】Codechef REBXOR

Description

Input

输入数据的第一行包含一个整数N,表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。

Output

输出一行包含给定表达式可能的最大值。

Sample Input

5
1 2 3 1 2

Sample Output

6

HINT

满足条件的(l1,r1,l2,r2)有:(1,2,3,3),(1,2,4,5),(3,3,4,5)。
对于100%的数据,2 ≤ N ≤ 4*105,0 ≤ Ai ≤ 109。

题解:如果只求一段异或和的最大值,我们直接用Trie树维护前缀异或和就好了,但这题要求两段,并且互不相交,那我们就维护一个前缀异或和的Trie树,维护一个后缀异或和的Trie数。然后扫两遍,分别记录ls[i]表示i和i左边的数构成连续的一段的最大异或和,rs[i]表示i和i右边的数构成连续的一段的最大异或和。然后直接用rs[i]和ls[i-1]的前缀最大值更新答案。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=400010;
int ch[maxn*32][2],ls[maxn],rs[maxn];
int n,v[maxn],tot,sum,ans,maxx;
void insert(int num)
{
	int i,d,u=1;
	for(i=1<<30;i;i>>=1)
	{
		d=(num&i)>0;
		if(!ch[u][d])	ch[u][d]=++tot;
		u=ch[u][d];
	}
}
int query(int num)
{
	int i,d,u=1,ret=0;
	for(i=1<<30;i;i>>=1)
	{
		d=!(num&i);
		if(ch[u][d])	u=ch[u][d],ret|=i;
		else	u=ch[u][d^1];
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	int i;
	tot=1,insert(0),sum=0;
	for(i=1;i<=n;i++)	scanf("%d",&v[i]),sum^=v[i],ls[i]=query(sum),insert(sum);
	tot=1,memset(ch,0,sizeof(ch)),insert(0),sum=0;
	for(i=n;i>=1;i--)	sum^=v[i],rs[i]=query(sum),insert(sum);
	maxx=-1<<30;
	for(i=1;i<=n;i++)	ans=max(ans,maxx+rs[i]),maxx=max(maxx,ls[i]);
	printf("%d",ans);
	return 0;
}
原文地址:https://www.cnblogs.com/CQzhangyu/p/6909332.html