F题 小苯的数组切分

https://ac.nowcoder.com/acm/contest/73854/F

显然，进行与运算的段是子数组内的最后一个元素，因此把这个元素去掉并加到答案上，题目转换成把一个子数组分割成一个非空前缀和一个非空后缀，使得它们的长度之和为子数组的长度，且答案最大。

观察到子数组内后缀的按位或和随着长度增大非严格递增，且变化的次数不会超过 次，这启示我们可以对每个按位或和相同的后缀长度的区间，计算出它们对应的前缀的异或和的最大值，并与按位或和相加，然后更新到答案上。

考虑如何计算对应的前缀的异或和的最大值，发现对应的前缀在原数组的下标也仍然连续，对原数组进行前缀异或，此时对应的前缀可以表示成 (l 为子数组左端点下标)，问题转换成查询前缀异或数组内子数组内任意元素与任意值的异或和的最大值，使用可持久化01字典树维护即可。

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define out(x) cout << #x << '=' << (x) << endl
#define out2(x, y) cout << #x << '=' << (x) << ',' << #y << '=' << (y) << endl 
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))

using namespace std;

using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

template<typename T> ostream & operator << (ostream &out,const set<T>&obj){out<<"set(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<*it;out<<")";return out;}
template<typename T1,typename T2> ostream & operator << (ostream &out,const map<T1,T2>&obj){out<<"map(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<it->first<<": "<<it->second;out<<")";return out;}
template<typename T1,typename T2> ostream & operator << (ostream &out,const pair<T1,T2>&obj){out<<"<"<<obj.first<<", "<<obj.second<<">";return out;}
template<typename T> ostream & operator << (ostream &out,const vector<T>&obj){out<<"vector(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<*it;out<<")";return out;}

const int maxn = 1e7;

struct node {
    int tr[2];
    int mx;
} tr[maxn];
int tot;

int qwq(int x) {
    tr[++tot] = tr[x];
    return tot;
}

void update(int &x, int v, int idx) {
    x = qwq(x);
    int cur = x;
    for (int i = 30; i >= 0; i--) {
        int &nxt = tr[cur].tr[v >> i & 1];
        nxt = qwq(nxt);
        tr[nxt].mx = idx;
        cur = nxt;
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    vector<int> rt(n + 1), pr(n + 1);
    for (int i = 1; i <= n; i++) {
        rt[i] = rt[i - 1];
        pr[i] = pr[i - 1] ^ a[i];
        update(rt[i], pr[i], i);
    }
    vector<array<int, 31>> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1];
        for (int j = 0; j < 31; j++) {
            if (a[i] >> j & 1) {
                pre[i][j] = i;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        sort(pre[i].begin(), pre[i].end(), greater<>());
    }
    auto query_trie = [&](int l, int r, int v) -> int { // max(p[l:r+1] ^ v)
        int cur = rt[r], ans = 0;
        for (int i = 30; i >= 0; i--) {
            int val = (v >> i & 1) ^ 1;
            if (tr[tr[cur].tr[val]].mx >= l) {
                ans |= 1 << i;
                cur = tr[cur].tr[val];
            } else {
                cur = tr[cur].tr[val ^ 1];
            }
        }
        return ans;
    };
    auto query = [&](int l, int r) -> ll {
        int add = a[r--];
        vector<array<int, 3>> range;
        int prepos = r + 1, val = 0;
        for (int pos : pre[r]) {
            if (pos <= l) break;
            if (pos == prepos) continue;
            range.push_back({pos + 1, prepos, val});
            val |= a[pos];
            prepos = pos;
        }
        range.push_back({l + 1, prepos, val});
        ll ans = 0;
        for (int i = 1; i < range.size(); i++) {
            auto [s, t, v] = range[i];
            ans = max(ans, 0LL + query_trie(s - 1, t - 1, pr[l - 1]) + v + add);
        }
        return ans;
    };
    cout << query(1, n) << endl;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
	//cin >> t;
    
    while (t--) {
    	solve(); 
	}
}