codeforces D. Mishka and Interesting sum 求区间内不同数的异或值

忘是亡心i 2022-07-18 16:20 162阅读 0赞

D. Mishka and Interesting sum

time limit per test

3.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Mishka enjoys programming. Since her birthday has just passed, her friends decided to present her with array of non-negative integers *a*1, *a*2, ..., *a**n* of *n* elements!

Mishka loved the array and she instantly decided to determine its beauty value, but she is too little and can't process large arrays. Right because of that she invited you to visit her and asked you to process *m* queries.

Each query is processed in the following way:

1.  Two integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ *n*) are specified — bounds of query segment.
2.  Integers, presented in array segment \[*l*,  *r*\] (in sequence of integers *a**l*, *a**l* + 1, ..., *a**r*) **even number of times**, are written down.
3.  XOR-sum of written down integers is calculated, and this value is the answer for a query. Formally, if integers written down in point 2 are *x*1, *x*2, ..., *x**k*, then Mishka wants to know the value ![ea4547ffed8a3c8eb751acf0531e94388122e790.png][], where ![7beade55e90846d70020a3d03521d3458b66751b.png][] — operator of exclusive bitwise OR.

Since only the little bears know the definition of array beauty, all you are to do is to answer each of queries presented.

Input

The first line of the input contains single integer *n* (1 ≤ *n* ≤ 1 000 000) — the number of elements in the array.

The second line of the input contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109) — array elements.

The third line of the input contains single integer *m* (1 ≤ *m* ≤ 1 000 000) — the number of queries.

Each of the next *m* lines describes corresponding query by a pair of integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ *n*) — the bounds of query segment.

Output

Print *m* non-negative integers — the answers for the queries in the order they appear in the input.

Examples

input

3
    3 7 8
    1
    1 3

output

input

7
    1 2 1 3 3 2 3
    5
    4 7
    4 5
    1 3
    1 7
    1 5

output

0
    3
    1
    3
    2

Note

In the second sample:

There is no integers in the segment of the first query, presented even number of times in the segment — the answer is 0.

In the second query there is only integer 3 is presented even number of times — the answer is 3.

In the third query only integer 1 is written down — the answer is 1.

In the fourth query all array elements are considered. Only 1 and 2 are presented there even number of times. The answer is ![f3f48ca9259e359e0f860214756305ac8291888b.png][].

In the fifth query 1 and 3 are written down. The answer is ![a1ba125fbec1b545761705318974b0be213f2ef2.png][].

题意： 求区间中出现次数为偶数次的数的异或值。

分析： 开始用莫队算法做，各种优化，但还是超时，因为复杂度是n\*sqrt(n)，后来看别人的思路：区间中出现偶数次的数的异或值等于区间中不同的数的异或值异或区间中出现次数为奇数次的数的异或值。区间中出现次数为奇数次的数的异或值恰好等于区间的异或值，因此只要求区间中不同的数的异或值就能求出区间中出现次数为偶数次的数的异或值。

区间中不同的数的异或值类比于求区间中不同的数的个数，有一种离线的方法：先把所有的询问按照右端点排序，排完序后遍历每一项，如果这个元素在以前出现过，那么删除掉他以前出现的位置，把当前位置设为他最后出现的位置。就是每个数只保留最右边的一个，可以用线段树或者树状数组来单点更新每个元素，然后查询前缀异或值。

复杂度：q\*log(n)

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    void Out(int a)
    {
        if(a>9)
            Out(a/10);
        putchar(a%10+'0');
    }
    const int N=1000010,MOD=1e9+7;
    int a[N],bit[N],b[N];
    struct st
    {
        int l,r,id;
    
    }q[N];
    void add(int i,int val)
    {
        for(;i<N;i+=i&-i) bit[i] ^= val;
    }
    int sum(int i)
    {
        int s=0;
        for(;i;i-=i&-i) s ^= bit[i];
        return s;
    }
    int lastPos[N];
    int ans[N],pre[N];
    bool cmp(st a,st b)
    {
        return a.r < b.r;
    }
    
    int main()
    {
        int n,m;
        while(~scanf("%d",&n))
        {
            for(int i=1;i<=n;i++){
                a[i] = in();
                b[i] = a[i];
                pre[i] = pre[i-1]^a[i];
            }
            sort(b+1,b+1+n);
            int mm = unique(b+1,b+1+n)-(b+1);
            for(int i=1;i<=n;i++){
                a[i] = lower_bound(b+1,b+mm,a[i])-b;
            }
            m=in();
            for(int i=1;i<=m;i++){
                q[i].l=in();
                q[i].r=in();
                q[i].id=i;
            }
            sort(q+1,q+m+1,cmp);
    
            for(int i=1,j=1;i<=m;i++){
                while(j<=q[i].r){
                    if(lastPos[a[j]]){
                        add(lastPos[a[j]],b[a[j]]);
                    }
                    lastPos[a[j]]=j;
                    add(j,b[a[j]]);
                    j++;
                }
                ans[q[i].id] = sum(q[i].r)^sum(q[i].l-1)^pre[q[i].r]^pre[q[i].l-1];
            }
    
            for(int i=1;i<=m;i++)
            {
                Out(ans[i]);
                putchar('\n');
            }
        }
        return 0;
    }

[ea4547ffed8a3c8eb751acf0531e94388122e790.png]: http://codeforces.com/predownloaded/ea/45/ea4547ffed8a3c8eb751acf0531e94388122e790.png
[7beade55e90846d70020a3d03521d3458b66751b.png]: /images/20220718/5121d0ea50c843859cdab1b9d0a6bebb.png
[f3f48ca9259e359e0f860214756305ac8291888b.png]: /images/20220718/3d36074f57c34e39af139dee196f1b98.png
[a1ba125fbec1b545761705318974b0be213f2ef2.png]: /images/20220718/6111fa27f0404e7dbe001d13cb9ac1b6.png