In this HackerEarth Substring Xor problem solution we have given a length-n array a and a number k, there are n x (n + 1) / 2 subarrays in total. For each subarray, we can compute the xor sum of its elements.

In this problem, we will sort all these xor-sums in non-increasing order. And we want to find the kth element.


HackerEarth Substring Xor problem solution


HackerEarth Substring Xor problem solution.

# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define vi vector < int >
# define pii pair < int , int >
# define mp make_pair
# define vii vector < pii >
# define pb push_back
# define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
IOS;
int n;
ll k;
fi>>n>>k;
const int Const = 19;
static int s[1 << 20];
for (int i = 1;i <= n;++i)
fi>>s[i],s[i] ^= s[i - 1];
static vector < array < int , 2 > > index;
static vi cnt;
index.pb({-1,-1});
cnt.pb(0);
auto next = [&](int pos,int bit)
{
if (index[pos][bit] == -1)
cnt.pb(0),index.pb({-1,-1}),index[pos][bit] = index.size() - 1;
pos = index[pos][bit];
return pos;
};
auto get = [&](int pos,int bit)
{
if (index[pos][bit] == -1)
return 0;
else
return cnt[index[pos][bit]];
};
for (int i = 0;i <= n;++i)
{
int pos = 0;
for (int t = Const;t + 1;--t)
++cnt[pos],pos = next(pos,(s[i] >> t) & 1);
++cnt[pos];
}
auto f = [&](int C)
{
ll ans = 0;
for (int i = 0;i <= n;++i)
{
int pos = 0;
for (int t = Const;pos != -1 && t + 1;--t)
{
int bit = ((C >> t) & 1) ^ ((s[i] >> t) & 1);
if (!((C >> t) & 1))
ans += get(pos,!bit);
pos = index[pos][bit];
}
ans += cnt[pos];
}
return ans;
};
int ans = 1 << 20;
for (int t = 1 << 19;t;t /= 2)
if (f(ans - t) < k + k)
ans -= t;
--ans;
fo << ans << '\n';
return 0;
}

Second solution

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

const int MAXN = 100000;

int main()
{
int n;
long long k;
assert(scanf("%d%lld", &n, &k) == 2 && 1 <= n && n <= MAXN && 1 <= k && k <= (long long)n * (n + 1) / 2);

vector<int> prefix;
prefix.push_back(0);
for (int i = 0; i < n; ++ i) {
int x;
assert(scanf("%d", &x) == 1);
assert(0 <= x && x < 1 << 20);
prefix.push_back(prefix.back() ^ x);
}

int answer = 0;
for (int bit = 19; bit >= 0; -- bit) {
// suppose this bit is 1
int current = answer ^ (1 << bit);
int mask = ((1 << 20) - 1) - ((1 << bit) - 1);
long long cnt = 0;
unordered_map<int, int> freq;
for (int i = 0; i < prefix.size(); ++ i) {
int target = (prefix[i] ^ current) & mask;
cnt += freq[target];
++ freq[prefix[i] & mask];
}
if (k <= cnt) {
answer = current;
} else {
k -= cnt;
}
}
printf("%d\n", answer);

return 0;
}