Xor-Subsequence (hard version) (Codeforces 1720D2)
Tags: DP, trees

It is the hard version of the problem. The only difference is that in this version $$$a_i \le 10^9$$$.You are given an array of $$$n$$$ integers $$$a_0, a_1, a_2, \ldots a_{n - 1}$$$. Bryap wants to find the longest beautiful subsequence in the array.An array $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$, where $$$0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$$$, is a subsequence of length $$$m$$$ of the array $$$a$$$.Subsequence $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$ of length $$$m$$$ is called beautiful, if the following condition holds:   For any $$$p$$$ ($$$0 \le p < m - 1$$$) holds: $$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$. Here $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$. For example, $$$2 \oplus 4 = 6$$$ and $$$3 \oplus 1=2$$$.Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$)  — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the length of the array.The second line of each test case contains $$$n$$$ integers $$$a_0,a_1,...,a_{n-1}$$$ ($$$0 \leq a_i \leq 10^9$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case print a single integer — the length of the longest beautiful subsequence.

Note: In the first test case, we can pick the whole array as a beautiful subsequence because $$$1 \oplus 1 < 2 \oplus 0$$$.In the second test case, we can pick elements with indexes $$$1$$$, $$$2$$$ and $$$4$$$ (in $$$0$$$ indexation). For this elements holds: $$$2 \oplus 2 < 4 \oplus 1$$$ and $$$4 \oplus 4 < 1 \oplus 2$$$.

Sample Inputs:
3
2
1 2
5
5 2 4 3 1
10
3 8 8 2 9 1 6 2 8 3

Sample Outputs:
2
3
6

Solution (Python):
import sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache, reduce
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, inf
if sys.version >= '3.8':
    from math import comb
RI = lambda : map(int, sys.stdin.buffer.readline().split())
RS = lambda : map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda : list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')
print = lambda d: sys.stdout.write(str(d) + '\n')
MOD = 10 ** 9 + 7
PROBLEM = 'https://codeforces.com/contest/1720/problem/D2\n\n输入 T(≤1e5) 表示 T 组数据。所有数据的 n 之和 ≤3e5。\n每组数据输入 n(2≤n≤3e5) 和长为 n 的数组 a(0≤a[i]≤1e9)，下标从 0 开始。\n\n构造一个严格单调递增的，元素范围在 [0,n-1] 的下标数组 id。\n要求 id 中的所有相邻元素 i 和 j，都满足 a[i] XOR j < a[j] XOR i。\n例如 a=[5,2,4,3,1]，构造 id=[1,2,4]，满足 a[1] XOR 2 < a[2] XOR 1 以及 a[2] XOR 4 < a[4] XOR 2。\n\n输出 id 的最大长度。\n输入\n3\n2\n1 2\n5\n5 2 4 3 1\n10\n3 8 8 2 9 1 6 2 8 3\n输出\n2\n3\n6\n'
''
''

def solve1():
    (n,) = RI()
    a = RILST()
    f = [defaultdict(lambda : [[0] * 2 for _ in range(2)]) for _ in range(30)]
    ans = 0
    for (i, v) in enumerate(a):
        mx = 0
        for k in range(30):
            mx = max(mx, f[k][(v ^ i) >> k + 1][v >> k & 1 ^ 1][i >> k & 1])
        mx += 1
        ans = max(ans, mx)
        for k in range(30):
            p = f[k][(v ^ i) >> k + 1]
            p[i >> k & 1][v >> k & 1] = max(p[i >> k & 1][v >> k & 1], mx)
    print(ans)

def solve2():
    (n,) = RI()
    a = RILST()
    f = [[[{} for _ in range(30)] for _ in range(2)] for _ in range(2)]
    ans = 0
    for (i, v) in enumerate(a):
        mx = 0
        for k in range(30):
            z = f[v >> k & 1 ^ 1][i >> k & 1][k].get((v ^ i) >> k + 1, 0)
            if z > mx:
                mx = z
        mx += 1
        ans = max(ans, mx)
        for k in range(30):
            z = f[i >> k & 1][v >> k & 1][k].get((v ^ i) >> k + 1, 0)
            if mx > z:
                f[i >> k & 1][v >> k & 1][k][(v ^ i) >> k + 1] = mx
    print(ans)

def solve3():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = {}
    for (i, v) in enumerate(a):
        cur = trie
        vi = i ^ v
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if p not in cur:
                cur[p] = {}
            z = cur.get((v >> j & 1 ^ 1) * 2 + (i >> j & 1) + 2, 0)
            if z > f[i]:
                f[i] = z
            cur = cur[p]
        f[i] += 1
        cur = trie
        for j in range(29, -1, -1):
            p = vi >> j & 1
            z = cur.get((i >> j & 1) * 2 + (v >> j & 1) + 2, 0)
            if z < f[i]:
                cur[(i >> j & 1) * 2 + (v >> j & 1) + 2] = f[i]
            cur = cur[p]
    print(max(f))

def solve4():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = [[], [], 0, 0, 0, 0]
    for (i, v) in enumerate(a):
        cur = trie
        vi = i ^ v
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if not cur[p]:
                cur[p] = [[], [], 0, 0, 0, 0]
            z = cur[(v >> j & 1 ^ 1) * 2 + (i >> j & 1) + 2]
            if z > f[i]:
                f[i] = z
            cur = cur[p]
        f[i] += 1
        cur = trie
        for j in range(29, -1, -1):
            p = vi >> j & 1
            z = cur[(i >> j & 1) * 2 + (v >> j & 1) + 2]
            if z < f[i]:
                cur[(i >> j & 1) * 2 + (v >> j & 1) + 2] = f[i]
            cur = cur[p]
    print(max(f))

def solve5():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = [[0, 0] for _ in range(n * 20 + 1)]
    dp = [[0, 0, 0, 0] for _ in range(n * 20 + 1)]
    size = 1
    for (i, v) in enumerate(a):
        vi = i ^ v
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            f[i] = max(f[i], dp[u][(v >> j & 1 ^ 1) * 2 + (i >> j & 1)])
            u = trie[u][p]
            if u == 0:
                break
        f[i] += 1
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if trie[u][p] == 0:
                trie[u][p] = size
                size += 1
            dp[u][(i >> j & 1) * 2 + (v >> j & 1)] = max(dp[u][(i >> j & 1) * 2 + (v >> j & 1)], f[i])
            u = trie[u][p]
    print(max(f))

def solve6():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = [[0] * (n * 30) for _ in range(2)]
    dp = [[0] * (n * 30) for _ in range(4)]
    size = 1
    for (i, v) in enumerate(a):
        vi = i ^ v
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            f[i] = max(f[i], dp[(v >> j & 1 ^ 1) * 2 + (i >> j & 1)][u])
            u = trie[p][u]
            if u == 0:
                break
        f[i] += 1
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if trie[p][u] == 0:
                trie[p][u] = size
                size += 1
            dp[(i >> j & 1) * 2 + (v >> j & 1)][u] = max(dp[(i >> j & 1) * 2 + (v >> j & 1)][u], f[i])
            u = trie[p][u]
    print(max(f))

def solve():
    (n,) = RI()
    a = RILST()
    trie = [[0] * (n * 30) for _ in range(2)]
    dp = [[0] * (n * 30) for _ in range(4)]
    ans = size = 1
    for (i, v) in enumerate(a):
        vi = i ^ v
        f = 0
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            z = dp[(v >> j & 1 ^ 1) << 1 | i >> j & 1][u]
            if z > f:
                f = z
            u = trie[p][u]
            if not u:
                break
        f += 1
        if f > ans:
            ans = f
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if not trie[p][u]:
                trie[p][u] = size
                size += 1
            z = dp[(i >> j & 1) << 1 | v >> j & 1][u]
            if z < f:
                dp[(i >> j & 1) << 1 | v >> j & 1][u] = f
            u = trie[p][u]
    print(ans)
if __name__ == '__main__':
    t = 1
    if t:
        (t,) = RI()
        for _ in range(t):
            solve()
    else:
        solve()

Solution (Python):
twopow = []
for i in range(30):
    twopow.append(2 ** i)
twopow.reverse()
maxN = int(60000000.0)
trie = [0] * maxN
for i in range(0, maxN, 6):
    trie[i] = trie[i + 1] = -1
idx_of_trie = 6

def get_next_idx_of_trie():
    global idx_of_trie
    idx_of_trie += 6
    return idx_of_trie - 6

def clear_trie():
    global idx_of_trie
    temp = idx_of_trie
    while idx_of_trie >= 1:
        idx_of_trie -= 1
        trie[idx_of_trie] = 0
    for i in range(0, temp, 6):
        trie[i] = trie[i + 1] = -1
    idx_of_trie = 6
bitmap = [(1, 0), (0, 0), (1, 1), (0, 1)]

def main():

    def add(i, ai):
        value = i ^ ai
        node = 0
        currmax = 1
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                if trie[node + 1] == -1:
                    trie[node + 1] = get_next_idx_of_trie()
                neighbour = trie[node]
                node = trie[node + 1]
            else:
                if trie[node] == -1:
                    trie[node] = get_next_idx_of_trie()
                neighbour = trie[node + 1]
                node = trie[node]
            if neighbour != -1:
                (jbit, ajbit) = bitmap[ibit * 2 + aibit]
                currmax = max(currmax, 1 + trie[neighbour + 2 + jbit * 2 + ajbit])
        node = 0
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                node = trie[node + 1]
            else:
                node = trie[node]
            trie[node + 2 + ibit * 2 + aibit] = max(currmax, trie[node + 2 + ibit * 2 + aibit])
        return currmax
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        ans = 0
        for (i, ai) in enumerate(a):
            res = add(i, ai)
            ans = max(ans, res)
        allans.append(ans)
        clear_trie()
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
twopow = []
for i in range(30):
    twopow.append(2 ** i)
twopow.reverse()
maxN = int(60000000.0)
trie = [0] * maxN
for i in range(0, maxN, 6):
    trie[i] = trie[i + 1] = -1
idx_of_trie = 6

def get_next_idx_of_trie():
    global idx_of_trie
    idx_of_trie += 6
    return idx_of_trie - 6

def clear_trie():
    global idx_of_trie
    temp = idx_of_trie
    while idx_of_trie >= 1:
        idx_of_trie -= 1
        trie[idx_of_trie] = 0
    for i in range(0, temp, 6):
        trie[i] = trie[i + 1] = -1
    idx_of_trie = 6
bitmap = [(1, 0), (0, 0), (1, 1), (0, 1)]

def main():

    def add(i, ai):
        value = i ^ ai
        node = 0
        currmax = 1
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                if trie[node + 1] == -1:
                    trie[node + 1] = get_next_idx_of_trie()
                neighbour = trie[node]
                node = trie[node + 1]
            else:
                if trie[node] == -1:
                    trie[node] = get_next_idx_of_trie()
                neighbour = trie[node + 1]
                node = trie[node]
            if neighbour != -1:
                (jbit, ajbit) = bitmap[ibit * 2 + aibit]
                currmax = max(currmax, 1 + trie[neighbour + 2 + jbit * 2 + ajbit])
        node = 0
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                node = trie[node + 1]
            else:
                node = trie[node]
            if currmax > trie[node + 2 + ibit * 2 + aibit]:
                trie[node + 2 + ibit * 2 + aibit] = currmax
        return currmax
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        ans = 0
        for (i, ai) in enumerate(a):
            res = add(i, ai)
            ans = max(ans, res)
        allans.append(ans)
        clear_trie()
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()