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.

樣例輸入復制

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

樣例輸出復制

2 4 0 1 4

解題報告：

? ?記錄每個數字出現的次數，奇數次說明這個數存在于答案中，偶數次相當于對答案沒有貢獻。打表找規律發現跟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 ; }

?

總結

以上是生活随笔為你收集整理的【计蒜客 - 2019南昌邀请赛网络赛 - K】MORE XOR（数学，找规律，打表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。