Xor sum

#include <bits/stdc++.h>

using namespace std;

#define bit(x, i) (x & (1 << i))  // select the bit of position i of x
#define lowbit(x) ((x) & ((x) ^ ((x) - 1)))  // get the lowest bit of x
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define BR "\n"
#define ALL(x) (x).begin(), (x).end()
#define IN(i, l, r) (l < i && i < r)
#define LINR(i, l, r) (l <= i && i <= r)
#define LIN(i, l, r) (l <= i && i < r)
#define INR(i, l, r) (l < i && i <= r)
#define REMAX(a, b) (a) = max((a), (b))
#define REMIN(a, b) (a) = min((a), (b));

// maps, pairs
#define mp make_pair
#define fi first
#define se second

// vectors
#define pb push_back
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;

using ll = long long;

const int INF = 1000000000;

struct XorSegTree {
  vi t;
  int n;

  XorSegTree(int a[], int n) : t(vi(4 * n + 1)), n(n) { build(a, 1, 0, n - 1); }

  int xorsum(int l, int r) { return xorsumrec(1, 0, n - 1, l, r); }
  void update(int pos, int v) { return updaterec(1, 0, n - 1, pos, v); }

 private:
  void updaterec(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
      t[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
        updaterec(v * 2, tl, tm, pos, new_val);
      else
        updaterec(v * 2 + 1, tm + 1, tr, pos, new_val);
      t[v] = t[v * 2] ^ t[v * 2 + 1];
    }
  }

  void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      t[v] = t[v * 2] ^ t[v * 2 + 1];
    }
  }

  int xorsumrec(int v, int tl, int tr, int l, int r) {
    if (l > r) {
      return 0;
    }
    if (l == tl && r == tr) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    return xorsumrec(v * 2, tl, tm, l, min(r, tm)) ^
           xorsumrec(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  }
};

int main() {
  // uncomment if io is a bottleneck
  // ios::sync_with_stdio(0);
  // cin.tie(0);

  // uncomment to read cin from a file
  // freopen("xor-sum.txt", "r", stdin);
  int n, q;
  cin >> n >> q;
  int a[n];
  REP(i, 0, n) { cin >> a[i]; }

  XorSegTree t(a, n);

  REP(i, 0, q) {
    int c, d;
    cin >> c >> d;

    cout << t.xorsum(c - 1, d - 1) << BR;
  }

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED