CF1592E Bored Bakry

Alex_Wei · 2021-10-20 09:19:31 · 题解

1592E. Bored Bakry

摘自 CF 比赛记录（密码可以私我 qwq）。

子区间 \rm and>xor，则其最高位一定相同且长度为偶数：因为长度为奇数时对于剩下来的所有位 d，若子区间第 d 位全为 1 则异或和也为 1，不优；而若至少有一个位置第 d 位为 0 则该位按位与为 0，不优。

上述结论是充要条件，因为 \rm xor 最高位为 0 而 \rm and 最高位为 1 故无论低位是什么都符合条件。所以直接枚举最高位就行。时间复杂度 \mathcal{O}(n\log a_i)。

const int N=1e6+5;
const int inf=0x3f3f3f3f;

int n,ans,a[N],pr[N],buc[2][1<<20];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)a[i]=read(),pr[i]=a[i]^pr[i-1]; 
    for(int i=20;~i;i--){
        mem(buc,-1);
        for(int j=1,r=1;j<=n;r=j=r+1){
            if((a[j]>>i&1)==0)continue;
            while(r<n&&(a[r+1]>>i&1))r++;
            for(int k=j-1;k<=r;k++){
                int res=pr[k]>>i+1;
                if(buc[k&1][res]==-1)buc[k&1][res]=k;
                else ans=max(ans,k-buc[k&1][res]);
            } for(int k=j-1;k<=r;k++)buc[k&1][pr[k]>>i+1]=-1;
        } 
    } cout<<ans<<endl;
    return 0;
}