U109923 字典树求调
查看原帖
U109923 字典树求调
961972
Lele_Programmer楼主2025/7/22 17:15
const int N=400005;
const int M=35;

int n;
int a[N];
int tr[N*M][2],idx=1;
int pre[N],sub[N];

void add(int k) {
    vector<int> vec;
    _rep(i,1,32) vec.emplace_back(k&1),k>>=1;
    reverse(vec.begin(),vec.end());
    int u=1;
    _iter(it,vec) {
        int i=*it;
        if (!tr[u][i]) tr[u][i]=++idx;
        u=tr[u][i];
    }
}

int query(int k) {
    vector<int> vec;
    _rep(i,1,32) vec.emplace_back(k&1),k>>=1;
    reverse(vec.begin(),vec.end());
    int u=1,ans=0;
    _iter(it,vec) {
        int i=*it;
        if (tr[u][i^1]) u=tr[u][i^1],ans=((ans<<1)^1);
        else u=tr[u][i],ans<<=1;
    }
    return ans;
}

int main() {
    read(n);
    _rep(i,1,n) read(a[i]);
    _rep(i,1,n) pre[i]=max(max(pre[i-1],a[i]),query(a[i])),add(a[i]);
    memset(tr,0,sizeof(tr)),idx=1;
    _rrep(i,n,1) sub[i]=max(max(sub[i+1],a[i]),query(a[i])),add(a[i]);
    i64 ans=0;
    _rep(i,1,n-1) ans=max(ans,(i64)pre[i]+sub[i+1]);
    write(ans);
    return 0;
}

61pts

2025/7/22 17:15
加载中...