HackerEarth Substring Xor problem solution

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.

# 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("%dn", answer);

    return 0;
}

coding problems