Given a sequence of nn numbers a1 ,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, j) (1≤i≤j≤n). For each xor-query (i, j)(i,j), you have to answer the result of function w(l,r).
Input
Line 1: t(1≤t≤20).
For each test case:
Line 1: n(1≤n≤100000).
Line 2: n numbers a1, a2 ,⋯,an(1≤ai≤10^9).
Line 33: q(1≤q≤100000), the number of xor-queries.
In the next q lines, each line contains 22 numbers i,j representing a xor-query(1≤i≤j≤n).
It is guaranteed that sum of nn and q≤10^6.
Output
For each xor-query (i, j)(i,j), print the result of function w(i,j)w(i,j) in a single line.
暴力打表找规律，维护前缀异或 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int a[maxn]; int b[4][maxn], c[4][maxn]; int dp1[4][maxn], dp2[4][maxn]; int main() { int T, n, m, l, r; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < 4; i++) { for (int j = 1; j <= n; j++) { if(j%4==i)b[i][j] = 1; if(j%4==i) { c[i][j]=1;c[i][j + 1] = 1; } } for (int j = 1; j <= n; j++) { dp1[i][j] = dp1[i][j - 1] ^ (b[i][j] * a[j]); dp2[i][j] = dp2[i][j - 1] ^ (c[i][j] * a[j]); } } scanf("%d", &m); while (m--) { scanf("%d%d", &l, &r); int k = (r - l + 1) % 4; if (k == 0) { printf("0\n"); } else if (k == 1) { for (int i = 0; i < 4; i++) { if(b[i][l]) { printf("%d\n", (dp1[i][l - 1] ^ dp1[i][r])); break; } } } else if (k == 3) { for (int i = 0; i < 4; i++) { if (b[i][l]==0 && b[i][l+1] == 1) { printf("%d\n", (dp1[i][l - 1] ^ dp1[i][r])); break; } } } else if (k == 2) { for (int i = 0; i < 4; i++) { if (c[i][l] == 1 && c[i][l + 1] == 1) { printf("%d\n", (dp2[i][l - 1] ^ dp2[i][r])); break; } } } } } return 0; } /* 11001100 01100110 00110011 10011001 1000 1000 1000 0100 0100 0100 0010 0010 0010 0001 0001 0001 */
