2128 前缀异或

基准时间限制：2 秒 空间限制：131072 KB 分值: 5 难度：1级算法题

---

输入一个长度为n(1<=n<=100000)n(1<=n<=100000)数组a[1],a[2],...,a[n]a[1],a[2],...,a[n]。

输入一个询问数m(1<=m<=100000)m(1<=m<=100000)和m组询问，每组询问形如(l,r)(l,r)

对于每组询问(l,r)(l,r)，你需要输出a[l]xora[l+1]xor...xora[r−1]xora[r]a[l]xora[l+1]xor...xora[r−1]xora[r]，即第l个数字到第r个数字的异或。

如果你的算法需要约n∗mn∗m的时间，你将只能通过第一个测试点。

如果你的算法需要约n+mn+m的时间，你将可以通过本题。

Input

第一行一个整数n

第二行为n个整数a[1], a[2], … a[n]

第三行一个整数m

接下来m行，每行两个整数l, r表示询问。

Output

输出一共m行，对于每一个询问输出一个整数表示结果。

Input示例

3

1 2 3

6

1 1

2 2

3 3

1 2

2 3

1 3

Output示例

1

2

3

3

1

0

wwwwodddd (题目提供者)

C++的运行时限为：2000 ms ，空间限制为：131072 KB 示例及语言说明请按这里

题解

我们知道Xor同一个数两次等于什么都没干，那么就令sum[i]=a[1] xor a[2] xor…xor a[i]，我们取答案时就sum[R] xor sum[L-1]就可以了。Xo r在C++里是 ^。

代码如下

#include
    
     using namespace std;int n,q,a[100005];int main(){//  freopen("prob.in","r",stdin);//  freopen("prob.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        a[i]^=a[i-1];    }    scanf("%d",&q);    for(int i=1;i<=q;i++){        int L,R;scanf("%d%d",&L,&R);        printf("%d\n",a[R]^a[L-1]);    }    return 0;}