AcWing 1414. 牛异或(Python)
原题链接
中等
作者:
习学学
,
2021-01-29 22:27:13
,
所有人可见
,
阅读 515
时间复杂度 o(nlog(n))
Python 代码
max_length = 2200000 # 最大的节点数,10^5 * 21 = 2.1 * 10^6
n = int(input())
nums = []
for _ in range(n):
nums.append(int(input()))
son = [[0] * 2 for _ in range(max_length)]
end = [0] * max_length
idx = 0
def insert(num, index):
global idx
cur = 0
for i in range(20, -1, -1):
bit = num >> i & 1
if son[cur][bit] == 0:
idx += 1
son[cur][bit] = idx
cur = son[cur][bit]
end[cur] = index
def query(num):
cur = 0
for i in range(20, -1, -1):
bit = num >> i & 1
if son[cur][~bit+2]: cur = son[cur][~bit+2]
else: cur = son[cur][bit]
return end[cur]
s = [0] * (n+1)
for i in range(n):
s[i+1] = s[i] ^ nums[i] # 前缀异或和
res, l, r = -1, 1, 1
for i in range(1, n+1):
insert(s[i-1], i-1) # 将前面的前缀和加入到Trie树中
k = query(s[i])
if s[k] ^ s[i] > res:
res = s[k] ^ s[i]
l, r = k+1, i
print(res, l, r)