题面

传送门

思路

这题其实蛮好想的......就是我考试的时候zz了，一直没有想到标记过的可以不再标记，总复杂度是$O(n)$

首先我们求个前缀和，那么$ans_i=max(pre[j]+pre[i]$ $xor$ $pre[j])$

考虑对于每个$pre[i]$，一个$pre[j]$在经过上述运算后增加的值

发现可以每一位拆开来考虑

那么有四种情况：$(p_i,p_j)=(0,0),(0,1),(1,0),(1,1)$

只有当$pre[i]$本位为0，$pre[j]$本位为1的时候，这一位会多出两倍的这一位的位值加入答案里面

那么相当于我们要对于前$i-1$个$pre$，求出真实值最大的一个二进制子集，满足这个子集在$pre[i]$里面都是0，而在某一个$1$到$i-1$的$pre[j]$中都是1

我们维护一个集合数组$s[i]$，表示$i$这个二进制组合有没有被目前已经加入的$pre[j]$覆盖

标记的时候从大的集合往子集里面走，遇到标记过的那就是肯定这个子集所有儿子都被标记过了，这样总的标记次数不会超过$O(max_{a_i})$

统计答案就很方便了，总时间复杂度$O(n\log m+m\log m)$（$m$是序列的最大值）

Code

乱搞第一定律：乱搞程序短小精悍

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#define ll long long

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

int n,pre[1000010],s[2000010];

inline void insert(int x){

	s[x]=1;

	for(int i=19;i>=0;i--){

		if(((x>>i)&1)&&(!s[x^(1<<i)])) insert(x^(1<<i));

	}

}

inline int query(int x){

	int re=0,i;

	for(i=19;i>=0;i--){

		if((!((x>>i)&1))&&(s[re|(1<<i)])) re|=(1<<i);

	}

	return re|x;

}

int main(){

	n=read();int i;

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

		insert(pre[i]=pre[i-1]^read());

		printf("%d ",(query(pre[i])<<1)-pre[i]);

	}

}

[NOI.AC省选模拟赛3.30] Mas的童年 [二进制乱搞]的相关教程结束。