凯旋而归
有 \(n\) 个数，第 \(i\) 个数为 \(a_i\) 。对于一个由 \(n\) 个数组成的序列 \(a\) ,定义它的帅气值\[f(a)=max\{(a_1xora_2xor...xora_i)+(a_{i+1}xora_{i+2}xor...xora_n)\}\]
现在给出 \(n\) 个数组成的序列 \(a\) ,求计算 \(a\) 的每个前缀的帅气值。
样例
5
1 2 3 4 5
1
3
6
10
9数据范围
\(n\le 456789,0\le a_i\le 10^6\)
分析
首先 \(a_i\) 不是很大，所以考虑到可以装桶。
我们假设已经处理出了序列 \(a\) 的前缀异或和序列 \(x\) 。
对于一个 \(x_i\) ，我们先把 \(x_r(1\le r<i)\) 装桶，具体方法是将 \(x_r\) 的每一个含 \(1\) 的子序列都装桶，如 \(x_r=1010\) （二进制），则将 \(1010,1000,0010\) 装桶。装桶使用dfs+剪枝，否则会 \(\text{Time Limit Exceeded}\) 飞掉。
然后我们设法把当前的前缀异或和 \(x_i\) 拆成两个前面已出现过的异或和，然后统计答案帅气值。
按位枚举 \(x_i\) ，在第 \(j\) 位上，若 \(x_{i,j}=1\) ，则答案的第 \(j\) 位必为 \(1\) ；
若 \(x_{i,j}=0\) 那么分出的两个异或和第 \(j\) 位要么都是 \(1\) 要么都是 \(0\) ，此时我们需要一个 \(now\) 变量，若 \(now\) 的某一位为 \(1\) ，则表明分出的两个异或和的的这一位都为 \(1\)， 否则那一位为 \(0\) ，我们判断当前的 \(now\) 是否在桶中出现过，若出现过，两个异或和第 \(j\) 位就是 \(1\) ，否则是 \(0\) 。
假设我们有这么一些数：
1001
0010
1010
1001
1000
程序执行步骤：
1.检查1001
当前桶中元素：空
| 位数 | \(now\) | \(ans\) |
|---|---|---|
| 1 | 0000 | 1000 |
| 2 | 0000 | 1000 |
| 3 | 0000 | 1000 |
| 4 | 0000 | 1001 |
2.1001,1000,0001装桶
3.检查1011
当前桶中元素：1001,1000,0001
| 位数 | \(now\) | \(ans\) |
|---|---|---|
| 1 | 0000 | 1000 |
| 2 | 0000 | 1000 |
| 3 | 0000 | 1010 |
| 4 | 0000 | 1011 |
4.1011,1001,1010,0011,1000,0010,0001装桶
5.检查0001
当前桶中元素：1011,1010,1001,1000,0011,0010,0001
| 位数 | \(now\) | \(ans\) |
|---|---|---|
| 1 | 1000 | 10000 |
| 2 | 1000 | 10000 |
| 3 | 1010 | 10100 |
| 4 | 1010 | 10101 |
6.0001装桶
7.检查1000
当前桶中元素：1011,1010,1001,1000,0011,0010,0001
| 位数 | \(now\) | \(ans\) |
|---|---|---|
| 1 | 0000 | 1000 |
| 2 | 0000 | 1000 |
| 3 | 0010 | 1100 |
| 4 | 0011 | 1110 |
8.1000装桶
9.检查0000
当前桶中元素：1011,1010,1001,1000,0011,0010,0001
| 位数 | \(now\) | \(ans\) |
|---|---|---|
| 1 | 1000 | 10000 |
| 2 | 1000 | 10000 |
| 3 | 1010 | 10100 |
| 4 | 1011 | 10110 |
10.1000装桶
输出结果：
9
11
21
14
22
Code
#include<cstdio>
#define maxn 456795
#define get(x,pos) bool((x)&(1<<(pos)))
using namespace std;
int read(){
char c=getchar();
int x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x;
}
void write(int x){
if(x>=10)write(x/10);
putchar(x%10+'0');
}
int b[1050000];
void add(int x){
if(b[x])return;
b[x]=1;
for(int i=20;i>=0;i--){
if(get(x,i)){
add(x-(1<<i));
}
}
}
int query(int x){
int now=0,ret=0;
for(int i=20;i>=0;i--){
if(get(x,i))ret|=1<<i;
else if(b[now|(1<<i)]){
now|=1<<i;
ret+=1<<(i+1);
}
}
return ret;
}
int main(){
int n=read(),a,x=0;
for(int i=1;i<=n;i++){
a=read();
x^=a;
write(query(x));
putchar('\n');
add(x);
}
return 0;
}
