【计蒜客 - 2019南昌邀请赛网络赛 - K】MORE XOR（数学，找规律，打表）

Given a sequence of nn numbers a_1, a_2, \cdots, a_na1,a2,⋯,an and three functions.

Define a function f(l,r)f(l,r) which returns \oplus a[x]⊕a[x] (l \le x \le rl≤x≤r). The \oplus⊕ represents exclusive OR.

Define a function g(l,r)g(l,r) which returns \oplus f(x,y)(l \le x \le y \le r)⊕f(x,y)(l≤x≤y≤r).

Define a function w(l,r)w(l,r) which returns \oplus g(x,y)(l \le x \le y \le r)⊕g(x,y)(l≤x≤y≤r).

You are also given a number of xor-queries. A xor-query is a pair (i, ji,j) (1 \le i \le j \le n1≤i≤j≤n). For each xor-query (i, j)(i,j), you have to answer the result of function w(l,r)w(l,r).

Input

Line 11: t (1 \le t \le 20)t(1≤t≤20).

For each test case:

Line 11: n (1 \le n \le 100000)n(1≤n≤100000).

Line 22: nn numbers a_1, a_2, \cdots, a_n (1 \le a_i \le 10^9)a1,a2,⋯,an(1≤ai≤109).

Line 33: q (1 \le q \le 100000)q(1≤q≤100000), the number of xor-queries.

In the next qq lines, each line contains 22 numbers i, ji,j representing a xor-query (1 \le i \le j \le n)(1≤i≤j≤n).

It is guaranteed that sum of nn and q \le 10^6q≤106.

Output

For each xor-query (i, j)(i,j), print the result of function w(i,j)w(i,j) in a single line.

样例输入复制

样例输出复制

解题报告：

记录每个数字出现的次数，奇数次说明这个数存在于答案中，偶数次相当于对答案没有贡献。打表找规律发现跟4的倍数有关，所以我们预处理以4为分组的异或和，然后O(1)输出结果就可以了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
ll a[MAX];
ll x0[MAX],x1[MAX],x2[MAX],x3[MAX];
ll all[MAX];
int main()
{
	int t;
	cin>>t;
	int n,q;
	while(t--) {
		scanf("%d",&n);
		for(int i = 1; i<=n; i++) {
			scanf("%lld",a+i);
			x0[i] = x0[i-1];
			x1[i] = x1[i-1];
			x2[i] = x2[i-1];
			x3[i] = x3[i-1];
			all[i] = all[i-1]^a[i];
			if(i%4==0) x0[i] ^= a[i];
			else if(i%4==1) x1[i] ^= a[i];
			else if(i%4==2) x2[i] ^= a[i];
			else if(i%4==3) x3[i] ^= a[i];
		}
		scanf("%d",&q);
		int l,r,len;
		ll ans;
		while(q--) {
			scanf("%d%d",&l,&r);
			len = r-l+1;
			if(len%2==0) {
				if(len%4==0) ans=0;
				else {
					if(l%4==0) {
						ans = x1[r]^x1[l];
						ans ^= x0[r]^x0[l-1];
					}
					else if(l%4==1) {
						ans = x2[r]^x2[l];
						ans ^= x1[r]^x1[l-1];
					}
					else if(l%4==2) {
						ans = x3[r]^x3[l];
						ans ^= x2[r]^x2[l-1];
					}
					else if(l%4==3) {
						ans = x0[r]^x0[l];
						ans ^= x3[r]^x3[l-1];
					}
				}
			}
			else {
				if(len%4 == 1) {				
					if(l%4==0) {
						ans = x0[r]^x0[l-1];					
					}
					else if(l%4==1) {
						ans = x1[r]^x1[l-1];						
					}
					else if(l%4==2) {
						ans = x2[r]^x2[l-1];
						
					}
					else if(l%4==3) {
						ans = x3[r]^x3[l-1];					
					}										
				}
				else {
					
					if(l%4==0) {
						ans = x1[r]^x1[l-1];					
					}
					else if(l%4==1) {
						ans = x2[r]^x2[l-1];						
					}
					else if(l%4==2) {
						ans = x3[r]^x3[l-1];						
					}
					else if(l%4==3) {
						ans = x0[r]^x0[l-1];						
					}										
				}
				
			}
			printf("%lld\n",ans);
		}
	}


	return 0 ;
}