题解：CF1777F Comfortably Numb / ARIS0_0 - 40

· · 题解

思路

方便讲述，我们设 f(l,r) 表示区间 [l,r] 的区间最大值，g(l,r) 表示区间异或和。

我们对序列分治，对于一个分治区间 [l,r]，我们考虑怎么消除 \max 这一约束。

先处理右区间，从左往右枚举 mid<i\le r，对于每个 i，找到一个最靠左的位置 j，满足：l\le j\le mid 且 f(j,mid)\le f(mid+1,i)，此时对于 j\le k\le mid，都满足 f(k,i)=f(mid+1,i)。

我们就只需要找到一个范围内的 k，满足 f(mid+1,i)\oplus g(mid+1,i)\oplus g(k,mid) 最大，可以将所有 g(k,mid) 插入字典树，然后在字典树上查询与 f(mid+1,i)\oplus g(mid+1,i) 异或结果最大的 g(k,mid) 就可以了。

左区间同理，注意每处理一半区间后需清空字典树，算完答案继续递归左右区间即可。

时间复杂度 O(n\log n\log V)，其中 V 是值域。

代码

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define fi first
#define se second
//#define int long long 
#define in(a) a = read()
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5 , mod = 998244353;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read() {
    int x = 0;
    char ch = getchar();
    bool f = 0;
    while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
    while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
    return f ? -x : x;
}
int a[N] , trie[N * 30][2] , tot , w[N * 30];
void insert(int x) {
    for(int i = 0 , j = 30 ; ~j ; j --) {
        int pos = (x >> j) & 1;
        if(!trie[i][pos]) trie[i][pos] = ++ tot;
        i = trie[i][pos];
    }
}
int query(int x) {
    int ans = 0;
     for(int i = 0 , j = 30 ; ~j ; j --) {
        int pos = (x >> j) & 1;
        if(trie[i][pos ^ 1]) ans |= (1 << j) , i = trie[i][pos ^ 1];
        else i = trie[i][pos];
    }
    return ans;
}
void into() {
    for(int i = 0 ; i <= tot ; i ++) trie[i][0] = trie[i][1] = 0;
    tot = 0;
}
int ans;
void solve(int l , int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    into();
    insert(0);
    for(int i = mid + 1 , j = mid , maxx = 0 , x = 0, pre = a[mid] , prv = a[mid] ; i <= r ; i ++) {
        maxx = max(maxx , a[i]);
        x ^= a[i];
        while(j >= l && prv <= maxx) {
            insert(pre);
            j --;
            pre ^= a[j] , prv = max(prv , a[j]);
        }
        ans = max(ans , query(maxx ^ x));
    }
    solve(l , mid) , solve(mid + 1 , r);
    into();
    insert(0);
    for(int i = mid , j = mid + 1 , maxx = 0 , x = 0 , pre = a[mid + 1] , prv = a[mid + 1] ; i >= l ; i --) {
        maxx = max(maxx , a[i]);
        x ^= a[i];
        while(j <= r && prv <= maxx) {
            insert(pre);
            j ++;
            pre ^= a[j] , prv = max(prv , a[j]);
        }
        ans = max(ans , query(maxx ^ x));
    }
}
signed main() {
    //cin_fast;
    int t;
    in(t);
    while(t --) {
        int n;
        in(n);
        int x = 0;
        for(int i = 1 ; i <= n ; i ++) in(a[i]);  
        ans = 0;
        solve(1 , n);
        cout << ans << '\n';
    }
    return 0;
}
/*
破碎后失去光芒的我
心生被光拯救的梦
不愿放手 太多光芒照亮了我
才期待着守护着以后
重回那蔚蓝的天空
日升月落 我仍是我
this is ARIS 40
*/