题目

给两个长度为n的数组a，b，请你计算出有多少个区间[l, r]，满足 （表示按位异或）

输入描述

第一行输入一个整数n，表示数组长度。 第二行输入n个整数。 第三行输入n个整数。

示例

input

5
1 2 3 4 5
5 4 3 2 1

output

3

满足条件的区间有[1,5],[2,4],[3,3]

思路

这道题如果直接暴力的话，需要两层循环来确定区间边界，确定区间之后还要对区间求异或和，这样时间复杂度就是

首先能想到的优化方法是，对区间进行异或和是不是可以像求和一样，使用前缀和？

异或运算满足交换律和结合律，这样通过递推可以算出[0,i)区间的异或和，其中

那么通过[0,i)和[0,j)能否算出[i,j)呢？

其实也是可以的，因为异或运算中，所以有

这样就节省了求异或和的时间，时间复杂度为

def f1(a: list, b: list, n: int) -> int:
    s = 0
    a_s = [0] + [s := s ^ i for i in a]
    s = 0
    b_s = [0] + [s := s ^ i for i in b]

    res = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            if a_s[j] ^ a_s[i] == b_s[j] ^ b_s[i]:
                res += 1
    return res

本来以为这样够优化了，结果提交代码只能过30%，时间复杂度还是太高。最后时间快到的时候才想到怎么优化

在上面的代码中，我用a_s[j] ^ a_s[i] == b_s[j] ^ b_s[i]这个式子来判断 a b 两个数组在[i, j)区间上的异或和是否相等，其实这个式子可以变形一下，变成a_s[i] ^ b_s[i] == a_s[j] ^ b_s[j]和前面的式子是等效的

所以这个问题可以转化为：已知边界 j ，求有多少个 i ，满足a_s[i] ^ b_s[i] == a_s[j] ^ b_s[j]。这样，我们就可以用哈希表记录有多少个a_s[i] ^ b_s[i]，key为a_s[i] ^ b_s[i]，value为个数，为了保证 i < j 我们在计算前缀和的同时，一边算个数，一边用哈希表统计。

def f2(a: list, b: list, n: int) -> int:
    # a_s[j] ^ a_s[i] == b_s[j] ^ b_s[i] 等价为 a_s[i] ^ b_s[i] == a_s[j] ^ b_s[j]
    a_s = [0 for i in range(n + 1)]
    b_s = [0 for i in range(n + 1)]
    d = {0: 1}
    res = 0
    for i in range(n):
        a_s[i + 1] = a_s[i] ^ a[i]
        b_s[i + 1] = b_s[i] ^ b[i]
        s = a_s[i + 1] ^ b_s[i + 1]
        res += d.get(s, 0)
        d[s] = d.get(s, 0) + 1
    return res

这样时间复杂度为，空间复杂度为 其实不需要用一个数组来存前缀和了，进一步优化

def f3(a: list, b: list, n: int) -> int:
    d = {0: 1}
    s = res = 0
    for i in range(n):
        s ^= a[i] ^ b[i]
        res += d.get(s, 0)
        d[s] = d.get(s, 0) + 1
    return res

为了验证算法的正确性，我写了一个程序对随机构造的数据进行验证

import random


def f1(a: list, b: list, n: int) -> int:
    s = 0
    a_s = [0] + [s := s ^ i for i in a]
    s = 0
    b_s = [0] + [s := s ^ i for i in b]

    res = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            if a_s[j] ^ a_s[i] == b_s[j] ^ b_s[i]:
                res += 1
    return res


def f2(a: list, b: list, n: int) -> int:
    # a_s[j] ^ a_s[i] == b_s[j] ^ b_s[i] 等价为 a_s[i] ^ b_s[i] == a_s[j] ^ b_s[j]
    a_s = [0 for i in range(n + 1)]
    b_s = [0 for i in range(n + 1)]
    d = {0: 1}
    res = 0
    for i in range(n):
        a_s[i + 1] = a_s[i] ^ a[i]
        b_s[i + 1] = b_s[i] ^ b[i]
        s = a_s[i + 1] ^ b_s[i + 1]
        res += d.get(s, 0)
        d[s] = d.get(s, 0) + 1
    return res


def f3(a: list, b: list, n: int) -> int:
    d = {0: 1}
    s = res = 0
    for i in range(n):
        s ^= a[i] ^ b[i]
        res += d.get(s, 0)
        d[s] = d.get(s, 0) + 1
    return res


def main():
    for i in range(100):
        n = random.randint(1, 10 ** 3)
        a = [random.randint(1, 10 ** 5) for i in range(n)]
        b = [random.randint(1, 10 ** 5) for i in range(n)]
        if f1(a, b, n) != f3(a, b, n):
            print('error')
            print(n)
            print(a)
            print(b)
            break


main()

经过验证，优化后的算法结果上和优化前的一致，说明算法是正确的

对三种方法测时，可以看到我们优化后对时间的提升是非常大的