/*
用所谓的加法拆分操作得到 x + y = (x ^ y) + 2 * (x & y)
那么我们这两段异或相当于前缀和 + 2 * 分段使左右两块&最大
记当前前缀异或和为S， 那么我们要找到优秀的X最大化（S^X) & X
显然贪心可行， 插入的时候维护当前数字所有子集， 打个vis标记， 就能快速查询了
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define mmp make_pair
#define M 3000100
using namespace std;
int read()
{
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
bool vis[M];
int n, a[M], s[M];
void insert(int x)
{
if(vis[x]) return;
vis[x] = true;
for(int i = 20; i >= 0; i--)
{
if(x & (1 << i)) insert(x ^ (1 << i));
}
}
int query(int x)
{
int ans = 0;
for(int i = 20; i >= 0; i--)
{
if(x & (1 << i)) continue;
if(vis[ans | (1 << i)]) ans |= (1 << i);
}
return ans;
}
int main()
{
n = read();
for(int i = 1; i <= n; i++)
{
a[i] = read();
s[i] = s[i - 1] ^ a[i];
}
for(int i = 1; i <= n; i++)
{
cout << s[i] + query(s[i]) * 2 << " ";
insert(s[i]);
}
return 0;
}
转载于:https://www.cnblogs.com/luoyibujue/p/10627933.html
