## Monday, August 22, 2016

### 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;
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()) {
}
last_pos[a[last_index]] = 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.