HackerEarth Shubham and Subarray Xor problem solution

In this HackerEarth Shubham and Subarray Xor problem solution You are given an array consisting of n integers a1,a2,...an. Find the maximum value of xor of sum of 2 disjoint subarrays i.e maximize ( sum(l1,r1) xor sum(l2,r2) )
where 1 <= l1 <= r1 < l2 <= r2 <= n.
Note: sum(l,r) denotes the sum of elements from indices l to r both inclusive.

HackerEarth Shubham and Subarray Xor problem solution.

`#include <iostream>#include<bits/stdc++.h>using namespace std;#define ll long long int#define inf 1000000000000#define mod 1000000007#define pb push_back#define mp make_pair#define all(v) v.begin(),v.end()#define S second#define F first#define boost1 ios::sync_with_stdio(false);#define boost2 cin.tie(0);#define mem(a,val) memset(a,val,sizeof a)#define endl "\n"#define maxn 820000ll tr[8*maxn][2],nn=1,cnt[8*maxn][2],arr[905],sum[905];void add(ll a) {    ll t = 1;    for (ll i = 31; i >= 0; --i) {        int now = (a >> i) & 1;        if (!tr[t][now]) {            tr[t][now] = ++nn;        }        cnt[t][now]++;        t = tr[t][now];    }}ll getMax(ll a) {    ll t = 1, res = 0;    for (ll i = 31; i >= 0; --i) {        ll now = (a >> i) & 1;        now = !now;        if (tr[t][now] && cnt[t][now]) {            t = tr[t][now];            res += (1 << i) * 1;        } else {            t = tr[t][!now];        }    }    return res;}inline ll getsum(ll l,ll r){    assert(l<=r);    return sum[r]-sum[l-1];}int main(){    boost1;boost2;    ll i,j,n,x,y,val,ans;    cin>>n;    for(i=1;i<=n;i++)    cin>>arr[i];    sum[1]=arr[1];    for(i=2;i<=n;i++)    sum[i]=sum[i-1]+arr[i];    add(arr[n]);    ans=0;    for(i=n-1;i>=1;i--)    {        for(j=i;j>=1;j--)        {            val=getsum(j,i);            ans=max(ans,getMax(val));        }        for(j=i;j<=n;j++)        {               val=getsum(i,j);            add(val);        }    }    cout<<ans;    return 0;}`

Second solution

`#include <bits/stdc++.h>using namespace std;#define next _nxtconst int N = 10000005;int sz = 0, next[2][N], arr[905], sum[905];bool created[N];void insert (int s) {    int v = 0;    for (int i = 30; i >= 0; i--) {        int c = (s >> i) & 1;        if (!created[next[c][v]]) {            next[c][v] = ++sz;            created[sz] = true;        }        v = next[c][v];    }}int search (int tmp) {    int v = 0, ans = 0;    for (int i = 30; i >= 0; i--) {        int c = (tmp >> i) & 1;        if(created[next[1 ^ c][v]]){            ans |= ((1 ^ c) << i);            v = next[1 ^ c][v];        }        else{            ans |= (c << i);            v = next[c][v];        }    }    return ans;}int main(){    int i,j,n,maxi = 0,curr;    scanf("%d", &n);    for(i = 1; i <= n; i++){        scanf("%d", &arr[i]);        sum[i] = sum[i - 1] + arr[i];    }    for(i = 1; i <= n; i++){        for(j = 1; j <= i; j++)            insert(sum[i] - sum[j - 1]);        for(j = i + 1; j <= n; j++)            maxi = max(maxi, (sum[j] - sum[i]) ^ search(sum[j] - sum[i]));    }    printf("%d\n", maxi);    return 0;}`