1863F - Divide XOR and Conquer - CodeForces Solution

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define int long long
using namespace std;
const int _=1e6+7;

void solve() {
    int n;
    cin>>n;

    vector<int> a(n+1),s(n+1);
    FOR(i,1,n) {
        cin>>a[i];
        s[i]=s[i-1]^a[i];
    }

    vector dp(n+1,vector<bool>(n+1,0));
    vector L(n+1,0ll),R=L;
    int js=0;

    for(int len=n;len>=1;--len) {
        for(int l=1,r=len;r<=n;++l,++r) {
            int x=s[r]^s[l-1];
            x|=(1ll<<60);

            dp[l][r]=(L[l]&x) | (R[r]&x);

            if(len==n) dp[l][r]=1;

            if(dp[l][r]==0) continue;

            int val= (s[r]^s[l-1]) > 0 ? (1ll<<__lg((s[r]^s[l-1]))) : ((1ll<<60));

            L[l]|=val;
            R[r]|=val;
        }
    }

    FOR(i,1,n) cout<<dp[i][i];
    cout<<"\n";
}
signed main() {
    #ifdef ONLINE_JUDGE
        ios::sync_with_stdio(false);cin.tie(0);
    #else
        freopen("a.in","r",stdin);
    #endif
    int T;
    cin>>T;
    while(T--) {
        solve();
    }   
    return 0;
}