BZOJ：5092 [Lydsy1711月赛]分割序列（贪心&高维前缀和）

Description

对于一个长度为n的非负整数序列b_1,b_2,...,b_n，定义这个序列的能量为：f(b)=max{i=0,1,...,n}((b_1 xor b

_2 xor...xor b_i)+(b_{i+1} xor b_{i+2} xor...xor b_n))其中xor表示按位异或(XOR)，给定一个长度为n的非

负整数序列a_1,a_2,...,a_n，请计算a的每个前缀的能量值。

Input

第一行包含一个正整数n(n<=300000)，表示序列a的长度。

第二行包含n个非负整数a_1,a_2,...,a_n(0<=a_i<=10^6)，依次表示a中每个元素的值。

Output

包含n行，每行一个整数，即a每个前缀的能量值。

Sample Input

5
1 2 3 4 5

Sample Output

1
3
6
10
9

题意：对数组的异或前缀和a[i]，对于每个i，求最大a[j]+a[j]^a[i]；

思路：从高位到第位贪心(20->0)，如果第i位为1，显然无论选0或者1够有一样的贡献。如果为0，我们优先选1；这次选了1后，后面选的应该包括这个1，即之前选的1的集合的超集。我们用高维前缀和来求每个数的超集的最小位置。如果最小位置小于等于i，说明这意味可以选1。

（这个公式还可以求最小位置ORZ。

（总觉得再CF做过类似的题，而且当时没做来

#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<20;
int a[maxn],f[maxn];
int main()
{
    memset(f,127,sizeof(f));
    int N; scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&a[i]);
        a[i]^=a[i-1];
        f[a[i]]=min(f[a[i]],i);
    }
    for(int i=0;i<20;i++){
        for(int j=0;j<(1<<20);j++)
          if(!(j&(1<<i))) f[j]=min(f[j],f[j|(1<<i)]);
    }
    for(int i=1;i<=N;i++){
        int ans=0,now=0;
        for(int j=19;j>=0;j--){
            if((a[i]>>j)&1) ans+=(1<<j);
            else if(f[now|(1<<j)]<=i) ans+=(1<<j)*2,now|=(1<<j);
        }
        printf("%d
",ans);
    }
    return 0;
}