Comfortably Numb (Codeforces 1777F)
Tags: Others, divide and conquer

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers.The numbness of a subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ (for arbitrary $$$l \leq r$$$) is defined as $$$$$$\max(a_l, a_{l+1}, \ldots, a_r) \oplus (a_l \oplus a_{l+1} \oplus \ldots \oplus a_r),$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation.Find the maximum numbness over all subarrays.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print one integer — the maximum numbness over all subarrays of the given array.

Note: For the first test case, for the subarray $$$[3, 4, 5]$$$, its maximum value is $$$5$$$. Hence, its numbness is $$$3 \oplus 4 \oplus 5 \oplus 5$$$ = $$$7$$$. This is the maximum possible numbness in this array.In the second test case the subarray $$$[47, 52]$$$ provides the maximum numbness.

Sample Inputs:
2
5
1 2 3 4 5
3
10 47 52

Sample Outputs:
7
47

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, color) = ([-1], [-1], [0])
    return (G0, G1, color)

def insert(x, c, l):
    j = 0
    for i in range(l, -1, -1):
        color[j] = c
        if x & pow2[i]:
            if not G1[j] ^ -1:
                G0.append(-1)
                G1.append(-1)
                color.append(0)
                G1[j] = len(color) - 1
            j = G1[j]
        else:
            if not G0[j] ^ -1:
                G0.append(-1)
                G1.append(-1)
                color.append(0)
                G0[j] = len(color) - 1
            j = G0[j]
    color[j] = c
    return

def xor_max(x, c, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not x & pow2[i]:
            if not G1[j] == -1 and color[G1[j]] == c:
                ans += pow2[i]
                j = G1[j]
            else:
                j = G0[j]
        elif not G0[j] == -1 and color[G0[j]] == c:
            ans += pow2[i]
            j = G0[j]
        else:
            j = G1[j]
    return ans
t = int(input())
ans = []
pow2 = [1]
l0 = 30
for _ in range(l0):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    (p, c) = (1, 1)
    ans0 = 0
    for _ in range(10):
        (l, m, r) = (0, p, min(2 * p, n))
        while m < r:
            (j, ma, xl, xr, u) = (m, 0, 0, 0, [])
            for i in range(m - 1, l - 1, -1):
                ai = a[i]
                xl ^= ai
                ma = max(ma, ai)
                while j < r and a[j] <= ma:
                    xr ^= a[j]
                    u.append(xr)
                    j += 1
                for k in u:
                    ans0 = max(ans0, xl ^ ma ^ k)
            (i, ma, xl, xr, u) = (m - 1, 0, 0, 0, [])
            for j in range(m, r):
                aj = a[j]
                xr ^= aj
                ma = max(ma, aj)
                while i >= l and a[i] <= ma:
                    xl ^= a[i]
                    u.append(xl)
                    i -= 1
                for k in u:
                    ans0 = max(ans0, xr ^ ma ^ k)
            (l, m, r) = (l + 2 * p, m + 2 * p, min(r + 2 * p, n))
        p <<= 1
    (G0, G1, color) = binary_trie()
    for _ in range(n.bit_length()):
        (l, m, r) = (0, p, min(2 * p, n))
        while m < r:
            (j, ma, xl, xr) = (m, 0, 0, 0)
            for i in range(m - 1, l - 1, -1):
                ai = a[i]
                xl ^= ai
                ma = max(ma, ai)
                while j < r and a[j] <= ma:
                    xr ^= a[j]
                    insert(xr, c, l0)
                    j += 1
                if color[0] == c:
                    ans0 = max(ans0, xor_max(xl ^ ma, c, l0))
            c += 1
            (i, ma, xl, xr) = (m - 1, 0, 0, 0)
            for j in range(m, r):
                aj = a[j]
                xr ^= aj
                ma = max(ma, aj)
                while i >= l and a[i] <= ma:
                    xl ^= a[i]
                    insert(xl, c, l0)
                    i -= 1
                if color[0] == c:
                    ans0 = max(ans0, xor_max(xr ^ ma, c, l0))
            c += 1
            (l, m, r) = (l + 2 * p, m + 2 * p, min(r + 2 * p, n))
        p <<= 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
from typing import *
from operator import add, xor, mul, ior, iand, itemgetter
import bisect
BUFSIZE = 4096
inf = float('inf')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

class Trie_01:

    def __init__(self, n=30):
        self.depth = n
        self.zero = None
        self.one = None

    def insert(self, num):
        tmp = self.depth
        node = self
        while tmp:
            tmp -= 1
            if num & 1 << tmp:
                if not node.one:
                    node.one = Trie_01(tmp)
                node = node.one
            else:
                if not node.zero:
                    node.zero = Trie_01(tmp)
                node = node.zero

    def findMaxXor(self, num):
        tmp = self.depth
        node = self
        ans = 0
        while tmp:
            tmp -= 1
            if num & 1 << tmp:
                if node.zero:
                    node = node.zero
                    ans += 1 << tmp
                else:
                    node = node.one
            elif node.one:
                node = node.one
                ans += 1 << tmp
            else:
                node = node.zero
        return ans

@bootstrap
def dfs(l, r):
    global ans
    if l == r:
        tries[l] = Trie_01()
        tries[l].insert(0)
        tries[l].insert(nums[l])
        carries[l] = 0
    else:
        idx = find_max[l, r]
        if idx == l:
            yield dfs(l + 1, r)
            new_idx = find_max[l + 1, r]
            trie = tries[new_idx]
            carry = carries[new_idx]
            ans = max(ans, trie.findMaxXor(carry))
            trie.insert(carry ^ nums[l])
            tries[idx] = trie
            carries[idx] = carry ^ nums[l]
            tries[new_idx] = None
        elif idx == r:
            yield dfs(l, r - 1)
            new_idx = find_max[l, r - 1]
            trie = tries[new_idx]
            carry = carries[new_idx]
            ans = max(ans, trie.findMaxXor(prefix_xor[l] ^ prefix_xor[r] ^ carry))
            trie.insert(prefix_xor[l] ^ prefix_xor[r + 1] ^ carry)
            tries[idx] = trie
            carries[idx] = carry
            tries[new_idx] = None
        else:
            yield dfs(l, idx - 1)
            yield dfs(idx + 1, r)
            if idx - l < r - idx:
                new_idx = find_max[idx + 1, r]
                trie = tries[new_idx]
                carry = carries[new_idx]
                for i in range(l, idx + 1):
                    ans = max(ans, trie.findMaxXor(prefix_xor[i] ^ prefix_xor[idx] ^ carry))
                for i in range(l, idx + 1):
                    trie.insert(prefix_xor[i] ^ prefix_xor[idx + 1] ^ carry)
                tries[idx] = trie
                carries[idx] = carry ^ prefix_xor[l] ^ prefix_xor[idx + 1]
                tries[find_max[l, idx - 1]] = None
                tries[find_max[idx + 1, r]] = None
            else:
                new_idx = find_max[l, idx - 1]
                trie = tries[new_idx]
                carry = carries[new_idx]
                for i in range(idx, r + 1):
                    ans = max(ans, trie.findMaxXor(prefix_xor[l] ^ prefix_xor[idx] ^ prefix_xor[idx + 1] ^ prefix_xor[i + 1] ^ carry))
                for i in range(idx, r + 1):
                    trie.insert(prefix_xor[l] ^ prefix_xor[i + 1] ^ carry)
                tries[idx] = trie
                carries[idx] = carry
                tries[find_max[l, idx - 1]] = None
                tries[find_max[idx + 1, r]] = None
    yield
t = II()
for _ in range(t):
    n = II()
    nums = LII()
    if n <= 400:
        max_numbness = 0
        for i in range(n):
            xor_sum = 0
            max_num = 0
            for j in range(i, n):
                xor_sum ^= nums[j]
                max_num = max(max_num, nums[j])
                max_numbness = max(max_numbness, xor_sum ^ max_num)
        print(max_numbness)
        continue
    left_larger = [-1] * n
    stack_left = [(-1, inf)]
    for i in range(n):
        num = nums[i]
        while stack_left[-1][1] <= num:
            stack_left.pop()
        left_larger[i] = stack_left[-1][0]
        stack_left.append((i, num))
    right_larger = [-1] * n
    stack_right = [(n, inf)]
    for i in range(n - 1, -1, -1):
        num = nums[i]
        while stack_right[-1][1] < num:
            stack_right.pop()
        right_larger[i] = stack_right[-1][0]
        stack_right.append((i, num))
    find_max = {}
    for (i, (x, y)) in enumerate(zip(left_larger, right_larger)):
        find_max[x + 1, y - 1] = i
    del stack_right, stack_left, left_larger, right_larger
    prefix_xor = [0] + list(accumulate(nums, xor))
    tries = [None] * n
    carries = [None] * n
    ans = 0
    dfs(0, n - 1)
    print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, color) = ([-1], [-1], [0])
    return (G0, G1, color)

def insert(x, c, l):
    j = 0
    for i in range(l, -1, -1):
        color[j] = c
        if x & pow2[i]:
            if not G1[j] ^ -1:
                G0.append(-1)
                G1.append(-1)
                color.append(0)
                G1[j] = len(color) - 1
            j = G1[j]
        else:
            if not G0[j] ^ -1:
                G0.append(-1)
                G1.append(-1)
                color.append(0)
                G0[j] = len(color) - 1
            j = G0[j]
    color[j] = c
    return

def xor_max(x, c, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not x & pow2[i]:
            if not G1[j] == -1 and color[G1[j]] == c:
                ans += pow2[i]
                j = G1[j]
            else:
                j = G0[j]
        elif not G0[j] == -1 and color[G0[j]] == c:
            ans += pow2[i]
            j = G0[j]
        else:
            j = G1[j]
    return ans
t = int(input())
ans = []
pow2 = [1]
l0 = 30
for _ in range(l0):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    (p, c) = (1, 1)
    ans0 = 0
    for _ in range(10):
        (l, m, r) = (0, p, min(2 * p, n))
        while m < r:
            (j, ma, xl, xr, u) = (m, 0, 0, 0, [])
            for i in range(m - 1, l - 1, -1):
                ai = a[i]
                xl ^= ai
                ma = max(ma, ai)
                while j < r and a[j] <= ma:
                    xr ^= a[j]
                    u.append(xr)
                    j += 1
                for k in u:
                    ans0 = max(ans0, xl ^ ma ^ k)
            (i, ma, xl, xr, u) = (m - 1, 0, 0, 0, [])
            for j in range(m, r):
                aj = a[j]
                xr ^= aj
                ma = max(ma, aj)
                while i >= l and a[i] <= ma:
                    xl ^= a[i]
                    u.append(xl)
                    i -= 1
                for k in u:
                    ans0 = max(ans0, xr ^ ma ^ k)
            (l, m, r) = (l + 2 * p, m + 2 * p, min(r + 2 * p, n))
        p <<= 1
    (G0, G1, color) = binary_trie()
    for _ in range(n.bit_length()):
        (l, m, r) = (0, p, min(2 * p, n))
        while m < r:
            (j, ma, xl, xr) = (m, 0, 0, 0)
            for i in range(m - 1, l - 1, -1):
                ai = a[i]
                xl ^= ai
                ma = max(ma, ai)
                while j < r and a[j] <= ma:
                    xr ^= a[j]
                    insert(xr, c, l0)
                    j += 1
                if color[0] == c:
                    ans0 = max(ans0, xor_max(xl ^ ma, c, l0))
            c += 1
            (i, ma, xl, xr) = (m - 1, 0, 0, 0)
            for j in range(m, r):
                aj = a[j]
                xr ^= aj
                ma = max(ma, aj)
                while i >= l and a[i] <= ma:
                    xl ^= a[i]
                    insert(xl, c, l0)
                    i -= 1
                if color[0] == c:
                    ans0 = max(ans0, xor_max(xr ^ ma, c, l0))
            c += 1
            (l, m, r) = (l + 2 * p, m + 2 * p, min(r + 2 * p, n))
        p <<= 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))