Language: C++

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

class wavelet_matrix {
public:
  using key_type = unsigned int;
  using value_type = key_type;
  using size_t = std::size_t;

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

#ifdef __has_builtin
    static size_t popcount(const size_t x) {
      //*
      static_assert(
        wordsize == 64,
        "this implementation is specialized for 64 bit unsigned integer");
      return __builtin_popcountll(x);
      //*/
      static_assert(
        wordsize == 32,
        "this implementation is specialized for 32 bit unsigned integer");
      return __builtin_popcount(x);
      //*/
    }
#else
    static size_t popcount(size_t x) {
      /*
      static_assert(
        wordsize == 64,
        "this implementation is specialized for 64 bit unsigned integer");
      x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
      x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
      x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
      return x * 0x0101010101010101ULL >> 56 & 0x7f;
      /*/
      static_assert(
        wordsize == 32,
        "this implementation is specialized for 32 bit unsigned integer");
      x = (x & 0x55555555) + (x >> 1 & 0x55555555);
      x = (x & 0x33333333) + (x >> 2 & 0x33333333);
      x = (x + (x >> 4)) & 0x0F0F0F0F;
      return x * 0x01010101U >> 24 & 0x3F;
      //*/
    }
#endif
    static size_t mask(const size_t x, const size_t k) {
      return x & ~(~static_cast<size_t>(0) << k);
    }

    class node_type {
    public:
      size_t sum;
      size_t bit;
      node_type() : sum(0), bit(0) {}
    };

    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(mask(t.bit, 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;
    }
    void build() {
      for (size_t i = 1; i < v.size(); i += 1) {
        v[i].sum = v[i - 1].sum + popcount(v[i - 1].bit);
      }
    }
  };

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

  size_t at_least(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)) {
        ret += rl - rf;
        first -= rf;
        last -= rl;
      }
      else {
        const size_t b = size() - v.all();
        first = b + rf;
        last = b + rl;
      }
    }
    return ret + (last - first);
  }
};
constexpr typename wavelet_matrix::size_t wavelet_matrix::bit_vector::wordsize;

#include <iostream>
#include <vector>

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

  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 wm(i, c);
    for (const auto e : a) {
      const auto t = e & pbit - 1;
      if (t && wm.at_least(0, n, pbit - t) & 1) {
        ans ^= pbit;
      }
    }
  }

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

  return 0;
}


Compiler output:
a.cc:14:45: error: 'numeric_limits' is not a member of 'std'
   14 |     static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;
      |                                             ^~~~~~~~~~~~~~
a.cc:14:66: error: expected primary-expression before '>' token
   14 |     static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;
      |                                                                  ^
a.cc:14:69: error: '::digits' has not been declared
   14 |     static constexpr size_t wordsize = std::numeric_limits<size_t>::digits;
      |                                                                     ^~~~~~
a.cc: In static member function 'static wavelet_matrix::size_t wavelet_matrix::bit_vector::popcount(wavelet_matrix::size_t)':
a.cc:20:18: error: non-constant condition for static assertion
   20 |         wordsize == 64,
      |         ~~~~~~~~~^~~~~
a.cc:25:18: error: non-constant condition for static assertion
   25 |         wordsize == 32,
      |         ~~~~~~~~~^~~~~