bzoj 4260: REBXOR Trie+乱搞

题目大意:

题解:

啊啊啊.

被这种SB题坑了半天.

求出异或前缀和后

从n到1枚举\(r_1\)的取值就好了啊.

用Trie 算出1 ~ \(r_1-1\)和\(a_{r_1}\)的异或最大值ans1

以及\(a_{r_1 + 1}\)和\(r_1 + 1\) ~ n的异或最大值ans2

用ans1 + max{ans2}更新答案就好了

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 600010;

struct Node{

	Node* ch[2];

	int siz;

}*null,*root[maxn];

Node mem[maxn*32],*it;

inline void init(){

	it = mem;

	null = it++;null->ch[0] = null->ch[1] = null;

	null->siz = 0;

}

Node* insert(Node *rt,int x,int d){

	Node *p = it++;*p = *rt;p->siz ++;

	if(d == -1) return p;

	int id = (x>>d)&1;

	p->ch[id] = insert(p->ch[id],x,d-1);

	return p;

}

int query(Node *p1,Node *p2,int x,int d){

	if(d == -1) return 0;

	int id = (x>>d)&1;

	if(p2->ch[id^1]->siz - p1->ch[id^1]->siz > 0)

		return (1<<d) | query(p1->ch[id^1],p2->ch[id^1],x,d-1);

	return query(p1->ch[id],p2->ch[id],x,d-1);

}

void dfs(Node *p){

	printf("siz = %d\n",p->siz);

	if(p->ch[0] != null){puts("-> ch[0] : ");dfs(p->ch[0]);}

	if(p->ch[1] != null){puts("-> ch[1] : ");dfs(p->ch[1]);}

	puts("return");

}

int a[maxn];

int main(){

	int n;read(n);init();root[0] = null;

	root[1] = insert(root[0],0,31);

	++n;

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

		read(a[i]);a[i] ^= a[i-1];

		root[i] = insert(root[i-1],a[i],31);

	}

	int ans = 0,max2 = 0;

	for(int i=n;i>=2;--i){

		max2 = max(max2,query(root[i],root[n],a[i],31));

		ans = max(ans,max2 + query(root[0],root[i],a[i],31));

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

	getchar();getchar();

	return 0;

}