bzoj 5092 [Lydsy1711月赛]分割序列——高维前缀和

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=5092

套路地弄一个前缀异或和，就变成 f[ i ]=max_{j=0}^{i} { s[ j ] + (s[ i ]^s[ j ]) }。再套路地考虑按位贪心。

然后看了题解。按位贪心不是确定 f[ i ] 的这一位是0还是1，而是确定这一位是否给答案贡献 bin[ j ] !

按位考虑，自己这一位如果是1，则 j 不管取在哪，都只有一种情况，就是向答案贡献 bin[ j ]；

　　自己这一位如果是0，则 j 的位置影响到这一位对答案的贡献是 0 还是 2*bin[ j ] 。

因为自己这一位是0了，又要有那样的贡献，所以 j 的这一位一定是1；做到这一位的时候已经知道更高的位上选择了哪些位为1，所以如果知道自己位置是否可以在满足更高的选了1的位仍旧选1的基础上把这一位也选上1的话就好了。

这里有很好的思路：不是求自己能否达到，而是预处理整个数组里符合这个条件的最靠前的位置！这样自然也能判断自己是否可行了。

即，预处理满足更高位确定、当前位为1、更低位随便的a[ ]的最靠前位置。

这个可以用高维前缀和来做。初值是 p[ a[ i ] ]=min{ p[ a[ i ] ] , i } ，倒着枚举 i 就不用取min了；没有出现的值的 p 是 n+1 ，p[ 0 ] = 0。

状态里的 0 表示不作要求，1表示必须为1；则从低到高位枚举，p[ i ]对（最高位到当前位固定、当前位到最低位是自己子集）的p[ j ]取min即可。

计算答案的时候注意因为 a[ i ]&bin[ j ] 而产生贡献的，不用算在和 p 有关的那个限制里。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=3e5+,M=,K=(<<)+;//K!=1e6!!!

int n,a[N],bin[M],p[K];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

int main()

{

  int mx=,lm;

  n=rdn();for(int i=;i<=n;i++)a[i]=rdn()^a[i-],mx=Mx(mx,a[i]);

  bin[]=;

  for(lm=;(bin[lm-]<<)<=mx;lm++)

    bin[lm]=bin[lm-]<<;

  bin[lm]=bin[lm-]<<;

  for(int i=;i<bin[lm];i++)p[i]=n+;

  for(int i=n;i;i--)p[a[i]]=i;

  p[]=;

  for(int t=;t<lm;t++)

    for(int i=;i<bin[lm];i++)

      if(!(i&bin[t]))

    p[i]=Mn(p[i],p[i|bin[t]]);

  for(int i=,ans=,lj=;i<=n;i++,ans=,lj=)

    {

      for(int j=lm-;j>=;j--)

    {

      if(a[i]&bin[j])

        {ans+=bin[j];continue;}//no lj|=bin[j]

      if(p[lj|bin[j]]<=i)

        {

          ans+=bin[j]<<;lj|=bin[j];

        }

    }

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

    }

  return ;

}