摘要
Title: 3000. 神奇的数组
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms

3000. 神奇的数组

题意

在数组a中，多少个区间满足，区间异或和等于区间和
思路

当加入一个数时，区间和一定大于等于异或和
- 因为异或上一个数，最完美的情况，就是两个数的每一位都是1和0搭配，这样两个数异或就是加和
- 比如 1(001) 和 6(110)，异或值和加和相等
- 如果不相等，那么往后再添加一个非负整数a，也不可能相等了，因为加和加a，但异或最多a，不可能再追回来了
  所以，这样是有单调性的，我们可以二分或者双指针求出答案
  比如二分，固定一个左端点，二分出最远的满足性质的右端点，区间内的所有数都是满足的
代码

# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor


class sa:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, a):
        return self.x < a.x


# Final
N = int(2e5 + 10)
M = 20
INF = int(2e9)

# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65  # A -> 0
NTL = lambda x: ascii_uppercase[x]  # 0 -> A

# —————————————————————Division line ——————————————————————

a, q, p = [0] * N, [0] * N, [0] * N

n, = read()
a[1:] = read()

for i in range(1, n + 1):
    q[i] = q[i - 1] + a[i]
    p[i] = p[i - 1] ^ a[i]


def check(l, r):
    return q[r] - q[l - 1] == p[r] ^ p[l - 1]


ans = 0
for i in range(1, n + 1):
    l, r = i, n
    while l < r:
        mid = l + r + 1 >> 1
        if check(i, mid):
            l = mid
        else:
            r = mid - 1
    if check(i, r):
        ans += (r - i + 1)
print(ans)

3000. 神奇的数组

题意

思路

代码