Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) F. Bits And Pieces

给定一个(n)个数字组成的数组(a)

问当索引(i,j,k)满足(ilt jlt k)时，(a_i|(a_j&a_k))的最大值

限制

(3le nle 10^6)

(0le a_ile 2 imes 10^6)

思路

明显可以从后往前枚举(a_i)，再利用SOSdp在(O(logn))的时限内求解

SOSdp可以快速获取在(a_i)之后是否存在某个数(r)，它是某两个数(a_j,a_k)进行与运算后的子集（(t&(a_j&a_k)=t)）

根据或运算的性质，如果(a_i)的第(j)位上已经存在(1)，那么我们就不需要让(r)的第(j)位上出现(1)

又因为要让结果最大，故优先让高位为(1)，故在查询时从高位向低位循环即可

程序

(498ms/2000ms)

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define pb push_back
#define eb emplace_back
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const double angcst=PI/180.0;
const ll mod=998244353;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

int a[1000050];
int dp[1<<21];

void add(int x,int p)
{
    if(p>20)
    {
        dp[x]++;
        return;
    }
    if(dp[x]>=2) //只要由两个数拥有x子集，那么这两个数与运算后的子集就有x
        return;
    add(x,p+1);
    if((x>>p)&1) //如果x的p位为1，可以去除后让x的子集继续插入
        add(x^(1<<p),p);
}

int query(int x)
{
    int r=0;
    per(i,20,0) //高位向低位，贪心让高位优先
        if(!(x&(1<<i))&&dp[r|(1<<i)]>=2) //若x在第i位已经是1就不需要管第i位（WA7）
            r|=(1<<i);
    return x|r;
}

void solve()
{
    int n;
    cin>>n;
    rep(i,1,n)
        cin>>a[i];
    add(a[n],0);
    add(a[n-1],0);
    int ans=0;
    per(i,n-2,1)
    {
        ans=max(ans,query(a[i]));
        add(a[i],0);
    }
    cout<<ans<<'
';
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}