题意

题目链接。

给你一个由 $n$ 个整数组成的数组 $a$ 。

你需要在所有三元组 $(i,j,k)$ 中找出 $a_{i} | ( a_{j} \& a_ {k} )$ 的最大值，使得 $i < j < k$ .

这里 $\&$ 表示 位与运算，而 $|$ 表示 位与运算。

由 Codeforces Better! 根据 DeepL 翻译。

解析

考虑 SOS dp。

用 $dp_{mask}$ 表示 $mask$ 及其超集中的所有状态的最右边的两个数，即这两个数的 $\&$ 为 $mask$ 或其超集中的某一个状态。

那么，我们依次枚举 $a_i$，然后取其逐位取反后的数 $(1<<bits)\oplus a_i$，再从高到低逐位尝试，即判断加入该位后的 $dp_{mask}$ 中的两个数是否都在 $i$ 右侧即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=3e6+5;
pi dp[N];
int n,a[N],bits,ans;
void add(int mask,int pos){
    if(!dp[mask].fi) dp[mask].fi=pos;
    else if(!dp[mask].se){
        // if(pos==dp[mask].fi) return;
        dp[mask].se=pos;
        if(dp[mask].fi>dp[mask].se) swap(dp[mask].fi,dp[mask].se);
    }
    else if(pos>dp[mask].se){
        dp[mask].fi=dp[mask].se;
        dp[mask].se=pos;
    }
    else if(pos>dp[mask].fi){//&&pos!=dp[mask].se
        dp[mask].fi=pos;
    }
}
void merge(int mask,int orimask){
    add(mask,dp[orimask].fi);
    add(mask,dp[orimask].se);
}
signed main(){
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        bits=max(bits,(int)log2(a[i]));
        add(a[i],i);
    }
    bits++;

    for(int i=0;i<bits;i++)
        for(int sta=(1<<bits)-1;sta>=0;sta--)
            if(!(sta&(1<<i)))
                merge(sta,sta^(1<<i));

    for(int i=1;i<=n-2;i++){
        int complement=a[i]^((1<<bits)-1);
        int tmp=0;
        for(int j=bits-1;j>=0;j--){
            if(complement&(1<<j)){
                if(dp[tmp^(1<<j)].se!=-1 && dp[tmp^(1<<j)].fi>i){
                    tmp^=(1<<j);
                }
            }
        }
        // if(dp[tmp].se!=-1 & dp[tmp].fi>i) ans=max(ans,a[i]^tmp);
        ans=max(ans,a[i]^tmp);
    }
    printf("%d\n",ans);
    return 0;
}