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

题意

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

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

限制

\(3\le n\le 10^6\)

\(0\le a_i\le 2\times 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<<'\n';
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}