Codeforces Round #365 (Div. 2) - D. Mishka and Interesting sum

Problem Statement:
http://codeforces.com/contest/703/problem/D

Summary:
Given array a[i] for N <= 10^6 integers, and M <= 10^6 queries (L, R): collect all integers in a[L..R] that occur even number of times, and compute their XOR. E.g. for a = {1, 2, 2, 3, 4, 4}, query (2, 7) returns 2 XOR 4 = 6. If no such element in a particular query, return 0.

Solution:
The solution employs interesting segment tree update technique. The observation is that the answer to the query (L, R) can be computed as the XOR of:
1.  XOR of all elements in L to R (where each integer that occurs even number of times will cancel each other out) with
2. XOR of all distinct elements in L to R.

Part 1 is trivial, part 2 is the hard part. The idea is to process the queries in prefix order. Sort the queries in increasing R order. For each integers x that we will encounter from left to right while we are processing the queries, we keep track of the last_pos[x] the right most position where we have seen this number.

Hence if we want to find the XOR of all distinct integers from L to R, all we need to do is to XOR all integers x on which the last_pos[x] is >= L. By maintaining a segment tree, we can compute and update the XOR in O(log N). For each new position of x, the mechanic of the update will be: first update segment tree at old position last_pos[x] to 0, then update last_pos[x] to newest last position, and finally update the segment tree at new last_pos[x] to x.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
using namespace std;
struct Query {
  int left;
  int right;
  int id;
};
int n;
map<int,int> last_pos;
vector<int> segtree;  // Containing XOR of distinct elements from [L, R].
void UpdateSegtree(int i, int val, int p=1, int L=0, int R=n-1) {
  if (R < i || i < L) return;
  if (L == R && L == i) {
    segtree[p] = val;
    return;
  }
  int M = (L+R)/2;
  UpdateSegtree(i, val, p*2, L, M);
  UpdateSegtree(i, val, p*2+1, M+1, R);
  segtree[p] = segtree[2*p] ^ segtree[2*p+1];
}
int RangeQuery(int S, int T, int p=1, int L=0, int R=n-1) {
  if (R<S || T<L) return 0;
  if (S <= L && R <= T) return segtree[p];
  int M = (L+R)/2;
  return RangeQuery(S, T, p*2, L, M) ^ RangeQuery(S, T, p*2+1, M+1, R);
}
int main(){
  scanf("%d",&n);
  vector<int> a(n, 0);
  vector<int> xor_sum(n, 0);
  for (int i=0;i<n;++i){
    scanf("%d",&a[i]);
    xor_sum[i] = a[i];
    if (i > 0) xor_sum[i] ^= xor_sum[i-1];
  }
  segtree.resize(4*n, 0);
  int m;
  vector<Query> queries;
  scanf("%d",&m);
  int l,r;
  for (int i=0;i<m;++i){
    scanf("%d%d",&l,&r);
    l--; r--;
    queries.push_back({l, r, i});
  }
  sort(queries.begin(), queries.end(), [](const Query& L, const Query& R) {
    return L.right < R.right;
  });
  vector<int> ans(m, 0);
  int last_index = 0;
  for (int i=0;i<m;++i){
    l = queries[i].left;
    r = queries[i].right;
    while (last_index <= r) {
      auto it = last_pos.find(a[last_index]);
      if (it != last_pos.end()) {
        UpdateSegtree(it->second, 0);
      }
      last_pos[a[last_index]] = last_index;
      UpdateSegtree(last_index, a[last_index]);
      ++last_index;
    }
    ans[queries[i].id] = xor_sum[r] ^ (l>0 ? xor_sum[l-1] : 0) ^ RangeQuery(l, r);
  }
  for (int i = 0; i < m; ++i) {
    printf("%d\n",ans[i]);
  }
  return 0;
}

Corollary: to compute property of distinct integers in (L, R), we can service the queries in prefix order (increasing R ordering) and extend the prefix from left to right, while keeping track of each last position of the integers along the way.