MORE XOR

标签： 思维 位运算

---

Given a sequence of nnn numbers $a1,a2,⋯ ,an$ and three functions.
Define a function $f(l,r)$ which returns $⊕a[x]$ The $⊕$presents exclusive OR.

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

Define a function $w(l,r)$ which returns$⊕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), you have to answer the result of function $w(l,r)$.
Problem From：The Preliminary Contest for ICPC China Nanchang National Invitational

Input

Line 1: $t$ (1≤t≤20).

For each test case:

Line 1: $n$ (1≤n≤100000).

Line 2: numbers $a1,a2,⋯ ,an$ (1≤ai​<=10^9).

Line 3: $q$(1≤q≤100000) the number of xor-queries.

In the next q lines, each line contains 2 numbers i,j representing a xor-query (1≤i≤j≤n).

It is guaranteed that sum of n and q≤10^6

Output

For each xor-query (i,j), print the result of function $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

题解

感觉比较恶心的一道找规律题，当时在考场没有找全规律（不过看其他大佬一会儿就找出来了，可能是我找答案的方法不够清奇吧orz）
首先这道题一看都跟前缀异或和有关。
f[l,r]就不用说了，和普通前缀和一样
g[l,r]怎么理解呢，可以看做是一个从（l,l）到（l,r）到（r,r）组成的上三角平面的f[x,y]的点全部异或起来。
你会发现如果把（1,1）到（r,r）这条线上的点全部异或起来答案等于sum[r]（从a1到ar的前缀和）
按照这个思想我们继续思考从（1,2）到（r,r-1）的规律,（1,3）到（r,r-2）等等
可以发现：
当n为奇数时:g[1,n] = sum2[n];（sum2[i]是sum[i]的前缀和）
当n为偶数时:g[1,n] = 0;
可以用容斥原理继续计算g[l,r],有如下规律
当l+r为偶数时:g[l,r] = sum2[r] ^ sum2[l - 2]
当l+r为奇数时:g[l,r] = 0
接着我们用相同的想法思考w[l,r]
发现在（l,l）,（l,r）,（r,r）这个区域中，有贡献的点（x,y）必须满足x + y是偶数
于是单独考虑x+y为奇数的斜线，最后发现w[l,r]是一个关于sum2[i]数组的以四为单位的前缀和与后缀和
就是大概这样:
sum3_1[n] = sum2[n] + sum2[n - 4] + sum2[n - 8]…
sum3_2[n] = sum2[n] + sum2[n + 4] + sum2[n + 8]…
具体的规律有些抽象，这里就不描述了（不知道如何描述..）

代码

#include<bits/stdc++.h>
#define N 1000010
#define debug system("pause") 
using namespace std;

int n, t, m, l, r;
int a[N];
int sum[N], sum2[N], sum3q[N], sum3h[N];

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        memset(sum, 0, sizeof(sum));
        memset(sum2, 0, sizeof(sum));
        memset(sum3q, 0, sizeof(sum));
        memset(sum3h, 0, sizeof(sum));
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
        for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] ^ a[i];
        for(int i = 1; i <= n; i ++) sum2[i] = sum2[i - 1] ^ sum[i];
        for(int i = 0; i <= n; i ++) 
            if(i >= 4) sum3q[i] = sum3q[i - 4] ^ sum2[i];
            else sum3q[i] = sum2[i];
        for(int i = n; i >= 0; i --)
            if(i + 4 <= n) sum3h[i] = sum2[i] ^ sum3h[i + 4];
            else sum3h[i] = sum2[i];
        scanf("%d", &m);    
        for(int i = 1; i <= m; i ++)
        {
            scanf("%d%d", &l, &r);
            if(l == r) {printf("%d\n", a[l]); continue;}
            int t = 0, x;
            int a = r - 2, a2 = r - 3;
            int b = l, b2 = l + 1;
            x = (a - (l - 2)) / 4 + 1;
            t = t ^ sum3q[a] ^ sum3q[a - x * 4];
            x = (a2 - (l - 2)) / 4 + 1;
            t = t ^ sum3q[a2] ^ sum3q[a2 - x * 4];
            x = (r - b) / 4 + 1;
            t = t ^ sum3h[b] ^ sum3h[b + x * 4];
            x = (r - b2) / 4 + 1;
            t = t ^ sum3h[b2] ^ sum3h[b2 + x * 4];
            printf("%d\n", t);
        }
    }
    return 0;
} 

心得

感觉当时在考场上比较慌，最后规律没找全，看来考试的时候还是要稳住心态，找规律时候也不要慌，打表找规律也是一种不错方法的。