Language: C++

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>

template <class Key> class wavelet_matrix {
  using size_t = std::size_t;

public:
  using key_type = Key;
  using value_type = Key;
  using size_type = size_t;

private:
  class bit_vector {
    static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;

    static size_t popcount(size_t x) {
      //*
      static_assert(
          wordsize == 64,
          "this implementation is specialized for 64 bit unsigned integer");
      x -= x >> 1 & 0x5555555555555555;
      x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
      x = x + (x >> 4) & 0x0F0F0F0F0F0F0F0F;
      return x * 0x0101010101010101 >> 56 & 0x7f;
      /*/
      static_assert(
          wordsize == 32,
          "this implementation is specialized for 32 bit unsigned integer");
      x -= x >> 1 & 0x55555555;
      x = (x & 0x33333333) + (x >> 2 & 0x33333333);
      x = x + (x >> 4) & 0x0F0F0F0F;
      return x * 0x01010101 >> 24 & 0x3F;
      //*/
    }

    class node_type {
      friend bit_vector;

      size_t sum;
      size_t bit;
      node_type() = default;
    };

    std::vector<node_type> v;

  public:
    bit_vector(const size_t size) : v(size / wordsize + 2) {}

    size_t rank(const size_t index) const {
      const node_type &t = v[index / wordsize];
      return t.sum +
             popcount(t.bit & ~(~static_cast<size_t>(0) << index % wordsize));
    }
    size_t all() const { return v.back().sum; }

    void set(const size_t index) {
      v[index / wordsize].bit |= static_cast<size_t>(1) << index % wordsize;
      v[index / wordsize + 1].sum += 1;
    }
    void build() {
      const size_t s = v.size();
      for (size_t i = 1; i != s; i += 1)
        v[i].sum += v[i - 1].sum;
    }
  };

  static bool test(const key_type x, const size_t k) {
    return (x & static_cast<key_type>(1) << k) != 0;
  }
  static void set(key_type &x, const size_t k) {
    x |= static_cast<key_type>(1) << k;
  }

  size_t size_;
  std::vector<bit_vector> vecs;

  size_t less(size_t first, size_t last, const key_type key) const {
    size_t ret = 0;
    size_t p = vecs.size();
    while (p != 0) {
      p -= 1;
      const bit_vector &v = vecs[p];
      const size_t rf = v.rank(first), rl = v.rank(last);
      if (!test(key, p)) {
        first -= rf;
        last -= rl;
      } else {
        ret += (last - first) - (rl - rf);
        const size_t b = size() - v.all();
        first = b + rf;
        last = b + rl;
      }
    }
    return ret;
  }

public:
  wavelet_matrix() = default;
  wavelet_matrix(const size_t bit_length, std::vector<key_type> a)
      : size_(a.size()), vecs(bit_length, bit_vector(size())) {
    const size_t s = size();
    std::vector<key_type> one;
    one.reserve(s);
    size_t p = vecs.size();
    while (p != 0) {
      p -= 1;
      bit_vector &v = vecs[p];
      size_t zi = 0;
      for (size_t i = 0; i < s; ++i) {
        if (!test(a[i], p)) {
          a[zi] = a[i];
          zi += 1;
        } else {
          v.set(i);
          one.push_back(a[i]);
        }
      }
      v.build();
      std::copy(one.cbegin(), one.cend(), a.begin() + zi);
      one.clear();
    }
  }

  size_t size() const { return size_; }

  size_t rangefreq(const size_t first, const size_t last, const key_type lower,
                   const key_type upper) const {
    assert(first <= last);
    assert(last <= size());
    assert(lower <= upper);

    return less(first, last, upper) - less(first, last, lower);
  }
  key_type quantile(size_t first, size_t last, size_t n) const {
    assert(first <= last);
    assert(last <= size());
    assert(n < last - first);

    key_type ret = 0;
    size_t p = vecs.size();
    while (p != 0) {
      p -= 1;
      const bit_vector &v = vecs[p];
      const size_t rf = v.rank(first), rl = v.rank(last);
      const size_t z = (last - first) - (rl - rf);
      if (n < z) {
        first -= rf;
        last -= rl;
      } else {
        set(ret, p);
        n -= z;
        const size_t b = size() - v.all();
        first = b + rf;
        last = b + rl;
      }
    }
    return ret;
  }
};
template <class Key>
constexpr typename wavelet_matrix<Key>::size_t
    wavelet_matrix<Key>::bit_vector::wordsize;

#include <iostream>
#include <vector>

int main() {
  using uint = unsigned int;
  uint bit = 28;

  uint n;
  std::cin >> n;
  std::vector<uint> a(n), b(n), c(n);
  for (auto &e : a)
    std::cin >> e;
  for (auto &e : b)
    std::cin >> e;
  uint ans = 0;

  if (n & 1) {
    for (const auto e : a)
      ans ^= e;
    for (const auto e : b)
      ans ^= e;
  }

  for (uint i = 1; i <= bit; ++i) {
    const uint pbit = static_cast<uint>(1) << i;
    for (uint j = 0; j < n; ++j) {
      c[j] = b[j] & pbit - 1;
    }
    wavelet_matrix<uint> wm(i + 1, c);
    for (const auto e : a) {
      const uint t = e & pbit - 1;
      if (t && wm.rangefreq(0, n, pbit - t, pbit) & 1) {
        ans ^= pbit;
      }
    }
  }

  std::cout << ans << std::endl;

  return 0;
}


Compiler output:
a.cc:16:45: error: 'numeric_limits' is not a member of 'std'
   16 |     static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;
      |                                             ^~~~~~~~~~~~~~
a.cc:16:66: error: expected primary-expression before '>' token
   16 |     static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;
      |                                                                  ^
a.cc:16:69: error: '::digits' has not been declared
   16 |     static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;
      |                                                                     ^~~~~~
a.cc: In static member function 'static wavelet_matrix<Key>::size_t wavelet_matrix<Key>::bit_vector::popcount(wavelet_matrix<Key>::size_t)':
a.cc:21:20: error: non-constant condition for static assertion
   21 |           wordsize == 64,
      |           ~~~~~~~~~^~~~~
In file included from /usr/include/c++/14/bits/stl_tempbuf.h:61,
                 from /usr/include/c++/14/bits/stl_algo.h:69,
                 from /usr/include/c++/14/algorithm:61,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_construct.h: In instantiation of 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = wavelet_matrix<unsigned int>::bit_vector::node_type; _Args = {}]':
/usr/include/c++/14/bits/stl_uninitialized.h:666:23:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<true>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = wavelet_matrix<unsigned int>::bit_vector::node_type*; _Size = long unsigned int]'
  666 |               std::_Construct(__val);
      |               ~~~~~~~~~~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:712:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = wavelet_matrix<unsigned int>::bit_vector::node_type*; _Size = long unsigned int]'
  710 |       return __uninitialized_default_n_1<__is_trivial(_ValueType)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  711 |                                          && __can_fill>::
      |                                          ~~~~~~~~~~~~~~~~
  712 |         __uninit_default_n(__first, __n);
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:779:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, allocator<_Tp>&) [with _ForwardIterator = wavelet_matrix<unsigned int>::bit_vector::node_type*; _Size = long unsigned int; _Tp = wavelet_matrix<unsigned int>::bit_vector::node_type]'
  779 |     { return std::__uninitialized_default_n(__first, __n); }
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1720:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(size_type) [with _Tp = wavelet_matrix<unsigned int>::bit_vector::node_type; _Alloc = std::allocator<wavelet_matrix<unsigned int>::bit_vector::node_type>; size_type = long unsigned int]'
 1720 |           std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1721 |                                            _M_get_Tp_allocator());
      |                                            ~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:558:9:   required from 'std::vector<_Tp, _Alloc>::vector(size_type, const allocator_type&) [with _Tp = wavelet_matrix<unsigned int>::bit_vector::node_type; _Alloc = std::allocator<wavelet_matrix<unsigned int>::bit_vector::node_type>; size_type = long unsigned int; allocator_type = std::allocator<wavelet_matrix<unsigned int>::bit_vector::node_type>]'
  558 |       { _M_default_initialize(__n); }
      |         ^~~~~~~~~~~~~~~~~~~~~
a.cc:49:37:   required from 'wavelet_matrix<Key>::bit_vector::bit_vector(wavelet_matrix<Key>::size_t) [with Key = unsigned int; wavelet_matrix<Key>::size_t = long unsigned int]'
   49 |     bit_vector(const size_t size) : v(size / wordsize + 2) {}
      |                                     ^~~~~~~~~~~~~~~~~~~~~~
a.cc:102:43:   required from 'wavelet_matrix<Key>::wavelet_matrix(size_t, std::vector<Key>) [with Key = unsigned int; size_t = long unsigned int]'
  102 |       : size_(a.size()), vecs(bit_length, bit_vector(size())) {
      |                                           ^~~~~~~~~~~~~~~~~~
a.cc:194:37:   required from here
  194 |     wavelet_matrix<uint> wm(i + 1, c);
      |                                     ^
/usr/include/c++/14/bits/stl_construct.h:119:7: error: 'wavelet_matrix<Key>::bit_vector::node_type::node_type() [with Key = unsigned int]' is private within this context
  119 |       ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:43:7: note: declared private here
   43 |       node_type() = default;
      |       ^~~~~~~~~