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

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1000000 + 10, Mod = 110119;
typedef long long  LL;
int ans[N], a[N], f[N], s[N];
int lowbit(int x)
{
return x & (-x);
}
int n;
int sum(int x)
{
int res = 0;
while(x >= 1)
{
res ^= ans[x];
x -= lowbit(x);
}
return res;
}
void update(int x, int c)
{
while(x <= n)
{
ans[x] ^= c;
x += lowbit(x);

}
}
struct node
{
int l, r, id;
}p[N];
int cmp(node x, node y)
{
return x.r < y.r;
}
int main()
{
int m;
while(cin>>n)
{
map<int, int> last;
memset(ans, 0, sizeof(ans));
for(int i = 1; i<=n; i++)
{
scanf("%d", &a[i]);
if(!last[a[i]]) last[a[i]] = i;
update(i, a[i]);
}
cin>>m;
for(int i = 1; i<=m; i++)
{
scanf("%d%d", &p[i].l, &p[i].r);
p[i].id = i;
f[i] = sum(p[i].r) ^ sum(p[i].l-1);
}
sort(p+1, p+1+m, cmp);
int temp = 1;
for(int i = 1; i<=m; i++)
{
for(int j = temp; j<= p[i].r; j++)
{
int id = last[a[j]];
if(id != j)
{
update(id, a[j]);
}
last[a[j]] = j;
}
temp = p[i].r;
s[p[i].id] = sum(p[i].r) ^ sum(p[i].l-1);
}
for(int i = 1; i<=m; i++)
{
printf("%d\n", f[i] ^ s[i]);
}
}
return 0;
}