bzoj 4260: Codechef REBXOR (01 Trie）

2022-11-05 09:19:36

链接： https://www.lydsy.com/JudgeOnline/problem.php?id=4260

题面：

4260: Codechef REBXOR

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 2596 Solved: 1142
[Submit][Status][Discuss]

Description

Input

输入数据的第一行包含一个整数N，表示数组中的元素个数。

第二行包含N个整数A1,A2,…,AN。

Output

输出一行包含给定表达式可能的最大值。

Sample Input

5
1 2 3 1 2

Sample Output

HINT

满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。

对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。

前缀和+后缀和维护，用dp[i] 代表从1-i区间异或和最大的值

实现代码;

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 4e5+;

int tot;

int ch[*M][];

ll val[*M],a[M],pre[M],nex[M],dp[M];

void init(){

    tot = ;

    ch[][] = ch[][] = ;

}

void ins(ll x){

    int u = ;

    for(int i = ;i >= ;i --){

        int v = (x>>i)&;

        if(!ch[u][v]){

            ch[tot][] = ch[tot][] = ;

            val[tot] = ;

            ch[u][v] = tot++;

        }

        u = ch[u][v];

    }

    val[u] = x;

}

ll query(ll x){

    int u = ;

    for(int i = ;i >= ;i --){

        int v = (x>>i)&;

        if(ch[u][v^]) u = ch[u][v^];

        else u = ch[u][v];

    }

    return x^val[u];

}

int main()

{

    ios::sync_with_stdio();

    cin.tie(); cout.tie();

    int n;

    cin>>n;

    init();

    for(int i = ;i <= n;i ++){

        cin>>a[i];

    }

    pre[] = nex[n+] = dp[] = ;

    for(int i = ;i <= n;i ++)

        pre[i] = pre[i-]^a[i];

    for(int i = n;i >= ;i --)

        nex[i] = nex[i+]^a[i];

    ins(pre[]);

    for(int i = ;i <= n;i ++){

        dp[i] = max(dp[i-],query(pre[i]));

        ins(pre[i]);

    }

    init();

    ins(nex[n+]);

    ll ans = ;

    for(int i = n;i >= ;i --){

        ans = max(ans,dp[i-]+query(nex[i]));

        ins(nex[i]);

    }

    cout<<ans<<endl;

}

码农公寓