牛客练习赛97 B

对于一个 $ll$，显然和它对应有贡献的 $rr$ 必定满足

直接扫描线+线段树即可。

（听说有高妙贪心写法？）

struct Seg1
{
    uint len;uint v;Seg1*L,*R;
    Seg1(uint n):L(NULL),R(NULL){v=-1;if((len=n)>1)L=new Seg1(n>>1),R=new Seg1(n-(n>>1));}
    voi And(uint l,uint r,uint w)
    {
        if(!l&&r==len){v&=w;return;}
        if(l<(len>>1))
            if(r<=(len>>1))L->And(l,r,w);
            else L->And(l,len>>1,w),R->And(0,r-(len>>1),w);
        else R->And(l-(len>>1),r-(len>>1),w);
    }
    uint Get(uint p)
    {
        if(len==1)return v;
        return v&(p<(len>>1)?L->Get(p):R->Get(p-(len>>1)));
    }
};
struct Seg2
{
    uint len;uint v;Seg2*L,*R;
    Seg2(uint n):L(NULL),R(NULL){v=0;if((len=n)>1)L=new Seg2(n>>1),R=new Seg2(n-(n>>1));}
    voi Or(uint l,uint r,uint w)
    {
        if(!l&&r==len){v|=w;return;}
        if(l<(len>>1))
            if(r<=(len>>1))L->Or(l,r,w);
            else L->Or(l,len>>1,w),R->Or(0,r-(len>>1),w);
        else R->Or(l-(len>>1),r-(len>>1),w);
    }
    uint Get(uint p)
    {
        if(len==1)return v;
        return v|(p<(len>>1)?L->Get(p):R->Get(p-(len>>1)));
    }
};
uint A[100005];
uint At[30];
int main()
{
    uint n;scanf("%u",&n);for(uint i=0;i<n;i++)scanf("%u",A+i);
    Seg1 S1(n);Seg2 S2(n);
    for(uint i=0;i<30;i++)At[i]=-1;
    uint ans=0;
    for(uint i=0;i<n;i++)
    {
        for(uint j=0;j<30;j++)if(A[i]>>j&1)At[j]=i;
        S1.And(0,i+1,A[i]),S2.Or(0,i+1,A[i]);
        for(uint j=0;j<30;j++)if(~At[j])
            _max(ans,S1.Get(At[j])+S2.Get(At[j]));
    }
    printf("%u\n",ans);
	return 0;
}